题解：P9062 [Ynoi2002] Adaptive Hsearch&Lsearch

not_clever_syl · 2024-12-19 08:47:26 · 题解

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

考虑沿用划分 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] 的都被偏序了。

然后可以发现这样剪枝很难卡，稠密的点和稀疏的点看起来都卡不了，所以可以跑到最优解第1。

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

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

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

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