题解：P9062 [Ynoi2002] Adaptive Hsearch&Lsearch

看不懂题解，所以我要乱搞。

考虑沿用划分 $d \times d$ 的网格的思路。

不妨钦定 $d=2^x$。

对于每个 $d$ 我们只求出距离 $\in [d,2d]$ 的点对。

现在我们考虑支配点对怎么搞，不妨只考虑 $j<i$ 的所有支配点对 $(j,i)$，记 $dis(j,i)$ 为点 $i,j$ 的距离。

支配点对有一个性质就是：若 $k<j<i$，$(k,i),(j,i)$ 均是支配点对，那么 $dis(k,i)<dis(j,i)$。

那么我们不妨考虑扫描线，枚举 $i=1 \sim n$。把 $i$ 周围的 $3 \times 3$ 网格的所有点拉出来算答案（需要保证编号 $\geq i$ 的点未加入哈希表），但是这样复杂度爆炸。

接下来是一个重要剪枝：维护一个指针 $mxp_{d,i}$ 表示当前枚举过的 $j$ 满足 $dis(j,i)<d$ 的最大的 $j$（注意 $j$ 需要在 $i$ 周围的 $3 \times 3$ 网格里），然后在枚举相邻矩阵算答案的时候从大到小枚举 $j$，如果 $dis(j,i)>2d$，就拿去更新 $mxp_{d,i}$，否则查看是否被偏序，如果没被偏序就加入支配点对里。

如果在枚举 $j$ 时 $j \leq mxp_{d,i}$ 或 $dis(j,i) < d$，那么可以 break 掉了，因为当前枚举的点对是 $\in[d,2d]$ 内的，所以更小的 $j$ 满足距离 $\in[d,2d]$ 的都被偏序了。

能证到枚举支配点对的过程上界最多是 $O(n^2)$ 的，不带 $\log$ 是因为：

对于一次 $d \times d$ 的划分，因为有上面的剪枝，一个 $i$ 能枚举到的实际上是距离 $\in [d,2\sqrt{2}d]$ 的点对，那么一个点对最多只能同时在三种边长不同的网格查询里。

可能枚举次数可以证到 $O(n \log V)$，但是我不会。

这种方法跑出来的支配点对可以直接用树状数组维护，甚至比分块维护快。