Solution

题意简述

二维平面上有 \(N\) 个点 \((x_1,y_1),\dots,(x_N,y_N)\) 和一个非负整数 \(D\)。

求有多少对点对 \((x,y)\) 满足 \(\sum\limits_{i=1}^N (|x-x_i|+|y-y_i|)\le D\)。

思路

发现 \(x_i\) 与 \(y_i\) 的捆绑关系不强（其实是几乎没有关联），所以我们分开考虑，也就是先考虑 \(\sum\limits_{i=1}^n|x-x_i|\)，得到结论后另外一边也是一样的。

见到绝对值先拆绝对值，我们可以先对 \(x_i\) 排个序，就可以通过枚举知道 \(x\) 的相对位置，结合前缀和，可以 \(O(1)\) 得到上面这个和式的值。设这个值为 \(A_x\)，我们可以直接枚举 \(x\in [-10^6,10^6]\)，然后 \(O(M)\) 得到 \(A_x\)。另外一边照葫芦画瓢，也可以快速得知 \(B_y\) 的值。

现在考虑计数。首先可以枚举值域内的每个 \(x\)，枚举中的子任务为求有多少个 \(y\) 满足 \(B_y\leq D-A_x\)。这是很简单的，对所有 \(B_y\) 排个序，二分答案即可。

code