本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-13 19:51:37

[ABC366E] Manhattan Multifocal Ellipse

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

• $1\le n\le 2\times 10^5$
• $0\le d\le 10^6$
• $\forall i\in[1,n],-10^6\le x_i,y_i\le 10^6$

由于 X 坐标和 Y 坐标互不相干，所以我们分开讨论。

我们将 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)$。
代码