「PA 2018」Ryki 题解

问题分析

我们有 $n$ 只熊，每只熊位于 $(x_i, y_i)$。当第 $k$ 只熊是 Limak 时，其他熊会按顺序吼叫并移动。每次吼叫时，其他熊会移动到离吼叫熊最近的相邻格子。

关键难点：

• 直接模拟 $O(n^2)$ 不可行（$n \leq 250,000$）
• 需要找到高效的数学方法计算最终位置

代码算法解析

这是一个基于区间合并和二维偏序的高效解法。

核心思想：独立处理坐标轴

关键观察：在八连通网格中，熊的移动在 $x$ 和 $y$ 坐标上是相对独立的。

算法流程

阶段一：预处理每个坐标轴上的移动区间

Solve(x, px, lx, rx, idx, rkx);  // 处理x坐标
Solve(y, py, ly, ry, idy, rky);  // 处理y坐标

Solve 函数为每个熊计算：

• px[i]：最终 $x$ 坐标
• lx[i], rx[i]：在 $x$ 坐标排序中的左右边界
• rkx[i]：在 $x$ 坐标排序中的排名

阶段二：计算基础总和

for (int i = 1; i <= n; i++)
    sum += (ll)px[i] * py[i];  // 所有熊最终位置乘积和

阶段三：修正 Limak 的影响

当第 $k$ 只熊是 Limak 时：

• 它不吼叫也不移动
• 这会影响其他熊的移动路径

通过二维偏序计算修正项：

// 添加各种修正区间
add(1, n, 1, ly[i], -1, 2, i);
add(1, n, ry[i], n, 1, 2, i);
add(1, lx[i], 1, n, -1, 3, i);
// ...

阶段四：使用树状数组统计修正

struct BIT {
    ll s[N];
    void add(int x, ll v) {
        while (x <= n) s[x] += v, x += x & -x;
    }
    ll qry(int x) {
        ll ans = 0;
        while (x) ans += s[x], x -= x & -x;
        return ans;
    }
} B1, B2, B3;

三个树状数组分别维护：

• B1：计数
• B2：$x$ 坐标相关和
• B3：$y$ 坐标相关和

算法正确性

数学原理：

1. 独立性：在八连通移动中，$x$ 和 $y$ 坐标的变化可以分开考虑
2. 区间性质：每只熊的移动影响可以表示为排序后的区间
3. 容斥原理：通过区间加减计算修正项

修正公式：

ans[i] = sum + (ll)x[i]*y[i] - (ll)(px[i] - (rkx[i]<=lx[i]) + (rkx[i]>=rx[i])) * 
                    (py[i] - (rky[i]<=ly[i]) + (rky[i]>=ry[i]));

复杂度分析

• Solve 函数：$O(n \log n)$，使用 set 进行区间合并
• 树状数组操作：$O(n \log n)$
• 总复杂度：$O(n \log n)$
• 空间复杂度：$O(n)$

关键数据结构

1. 并查集：f[], fl[], fr[] 用于区间合并
2. set：维护当前活跃区间
3. 树状数组：高效统计二维偏序
4. 向量数组：存储待处理区间

算法标签

• 数学推导
• 离散化

示例验证

对于样例：

4
3 5
2 1
1 4
2 1

算法会：

1. 分别对 $x$ 和 $y$ 坐标排序和预处理
2. 计算基础总和 sum
3. 对每个可能的 Limak 位置计算修正
4. 输出四个结果：27, 24, 25, 35

---

总结

这个解法通过巧妙的数学洞察：

1. 将八连通移动分解为坐标轴独立的区间操作
2. 使用区间合并预处理移动模式
3. 利用树状数组高效计算修正项
4. 在 $O(n \log n)$ 时间内解决大规模问题

该算法展示了如何将复杂的几何运动问题转化为高效的区间处理问题，是计算几何与数据结构结合的典范。