[ABC366E] Manhattan Multifocal Ellipse 讲解

· · 题解

[ABC366E] Manhattan Multifocal Ellipse

题目考察：排序，二分，前缀和。（但需要一定的思维）
题目简述： 给你 n 个点，第 i 个点的坐标是 (x_i,y_i)，求有多少个点 (a,b) 使得 (\sum_{i=1}^n|x_i-a|+|y_i-b|)\le d。
数据范围：

我们将 X 坐标和 Y 坐标分别排序。由于 |x_i-a|+|y_i-b|\le d 的点 (a,b) 才有贡献（i\in[1,n]），那么 |x_i-a|\le d 且 |y_i-b|\le d 的点才有可能做出贡献。
我们枚举 X 坐标，设 num_i 为当 X 坐标为 i-2\times 10^6 时 X 坐标与其他点的 X 坐标的距离，sumx_i 就等于 \displaystyle\sum_{j=1}^ix_i，那么 num_p 等于（下面的 id 指在序列中满足 x_{id-1}<p-2\times 10^6 且 x_{id}\ge p-2\times 10^6 的唯一的一个数）：

\begin{aligned}num_p&=\sum_{i=1}^n|p-2\times 10^6-x_i|\\&=|\sum_{i=1}^{id-1}p-2\times 10^6-x_i|+|\sum_{i=id}^nx_i-p+2\times 10^6|\\&=|(p-2\times 10^6)(id-1)-\sum_{i=1}^{id}x_i|+|(\sum_{i=id+1}^nx_i)-(p-2\times 10^6)(n-id+1)|\\&=|(p-2\times 10^6)(id-1)-sumx_i|+|sumx_n-sumx_i-(p-2\times 10^6)(n-id+1)|\end{aligned}

这样我们就能求出它们之间的距离了。

然后我们设 res_j 等于 \displaystyle\sum_{i=0}^Vnum_i=j（V 是值域），再对 res 求前缀和。

再看 Y 坐标，跟上面一样求出 Y 坐标与其他店的 Y 坐标的总距离，设其为 id，若 id\le d，则它的贡献就是 res_{d-id}。

时间复杂度为 \Theta(V\log n)。
代码