题解：P3483 [POI 2009] STR-Fire Brigade

· · 题解

这道题咋没有题解，调了我好久

题意：二维平面上有 z 个点，给定 p 个询问，每次两个点 P1、P2，求距离 P1 更近的点的个数、距离 P2 更近的点的个数以及与 P1、P2 距离相同的点的个数。距离为曼哈顿距离，横坐标值域为 [1,n]，纵坐标值域为 [1,m]。

首先发现只需要考虑处理距离 P1 更近的点即可，因为问题的对称性。

以下记点 A 的横坐标为 X_A，纵坐标为 Y_A。对于 z 个点中的任意一个点 A，我们列出关系式：|X_A - X_{P1}| + |Y_A - Y_{P1}| < |X_A - X_{P2}| + |Y_A - Y_{P2}|。

根据初中数学知识，X_A、Y_A 都有 3 种情况，一共 9 种情况，我们把它们在图像中表示出来。假设给定的 X_{P1} \le X_{P2}，Y_{P1} \le Y_{P2}。

rt，显然区域 2、4、6、8，区域 1、9，区域 3、7，区域 5 为四种不同情况，以下进行分讨：

记 a = X_{P2} - X_{P1}，b = Y_{P2} - Y_{P1}

  1. 区域 2、4、6、8

以区域 8 为例，\operatorname{dist}(P1,A) = \Delta y + (a - \Delta x) + b，\operatorname{dist}(P2,A) = \Delta x + \Delta y。

要保证 \operatorname{dist}(P1,A) < \operatorname{dist}(P2,A)，即要保证 \Delta y + (a - \Delta x) + b < \Delta x + \Delta y，即 \Delta x > \frac{a + b}{2}，带入 \Delta x = X_{P2} - X_A 得 X_A < X_{P2} - \frac{a + b}{2}。

因而该区域满足条件的点 A 需满足 X_A \in [X_{P1},X_{P2}] \cap [0,X_{P2} - \frac{a + b}{2})，Y_A \in (Y_{P2}, m]。

  1. 区域 1、9

以区域 9 为例，显然 \operatorname{dist}(P1,A) > \operatorname{dist}(P2,A)。（当然 P1 = P2 的情况需要特判）

因此该区域所有点均不满足。

  1. 区域 3、7

以区域 7 为例，\operatorname{dist}(P1,A) = \Delta x + \Delta y + b，\operatorname{dist}(P2,A) = \Delta x + \Delta y + a。

可以发现当 b < a 时 \operatorname{dist}(P1,A) < \operatorname{dist}(P2,A)。

所以当 b < a 时该区域所有点均满足。

  1. 区域 5

区域 5 中，\operatorname{dist}(P1,A) = (a - \Delta x) + (b - \Delta y)，\operatorname{dist}(P2,A) = \Delta x + \Delta y。

要保证 \operatorname{dist}(P1,A) < \operatorname{dist}(P2,A)，即要保证 (a - \Delta x) + (b - \Delta y) < \Delta x + \Delta y，即 \Delta x + \Delta y > \frac{a + b}{2}，带入 \Delta y = Y_{P2} - Y_A、\Delta x = X_{P2} - X_A 得 X_A + Y_A < X_{P2} + Y_{P2} - \frac{a + b}{2}。

因而该区域满足条件的点 A 需满足 X_A \in [X_{P1},X_{P2}]，Y_A \in [Y_{P1}, Y_{P2}]，X_A + Y_A \in [0, X_{P2} + Y_{P2} - \frac{a + b}{2})。

到这儿分类讨论结束。

如果 P1、P2 不是偏序关系怎么办？一开始我想的是再分讨一次，但是太麻烦，我们可以考虑将整个平面反转。具体的，我们考虑翻转 (1,1)(n,m) 这个矩形，若是左右翻转则所有横坐标 X 变为 n + 1 - X，若是上下翻转则所有纵坐标 Y 变为 m + 1 - Y。

现在尝试维护答案。我们发现前三类只与 X_A，Y_A 有关，且均为一段区间，考虑二维偏序，扫描线 + 树状数组即可。

第 4 类（即区域 5）另外有个 X_A + Y_A 的限制，是三维偏序。第一次打的时候用了二维线段树，空间爆炸喜提暴力分，于是专门新学了 KD-Tree 来用。

不幸的是，KD-Tree 常数过大，加上代码自带大常数，无法 AC。

尝试优化。我们在统计答案的时候换一个思路：统计 \operatorname{dist}(P1,A)<\operatorname{dist}(P2,A)、与 \operatorname{dist}(P1,A)\le\operatorname{dist}(P2,A) 的点的数量 a1、a2。后者只是在原先的推导上，将小于改为小于等于。那么其实它们有很多询问是重叠的，甚至是相同的，可以在相同的时候一块维护。

注意三个答案要变为 a1，z - a2，a2 - a1。

另外，KD-Tree 的询问速度较慢，可以把询问排一下序，相邻相同的询问使用同一个答案。

最后再加上一些各类广为人知的卡常技巧就可以 AC 啦。

Code