Sol P12506

· · 题解

考虑 $n\le 10^5$。我们有以下两个结论： - 如果一个点 $i$ 和 $i+n$ 在一个集合中，则与 $i$ 连通的所有点 $j$ 都一定合法，即 $j$ 和 $j+n$ 在一个集合中。 - 证明很简单，令原平面上 $j$ 能通过 $d$ 步跳到 $i$，如果 $d\equiv 0\pmod 2$ 则 $j\to i\to i+n\to j+n$ 是一条可行的方案，否则 $j\to i+n\to i\to j+n$ 是一条可行方案。 - 如果有一个集合 $S$ 满足 $S$ 中的点在原平面上能互相到达，且 $|S|\ge 3$，则 $S$ 中所有点均可行。 - 证明：如果 $i\in S$，那么可以找到 $j_1,j_2$ 满足 $j_1\in S,j_2\in S,j_1\ne j_2,j_1\ne i,j_2\ne i$，此时在原平面 $i\to j_1\to j_2\to i$ 即为一种可行的方案。因为 $|S|\ge 3$，所以一定能找到 $j_1,j_2$。 把平面分成若干个 $B\times B$ 的矩形，满足一个 $B\times B$ 矩形内的点均可以互相到达，对于一个矩形，令矩形内的这些点集合为 $S$，那么如果 $|S|\ge 3$，就直接 $\forall i\in S$，$i$ 和 $i+n$ 合并即可。 取 $B=\dfrac{r}{2}$，令 $S_{i,j}=\{(x_k,y_k)\mid iB\le x_k<(i+1)B,jB\le y_k<(j+1)B\}$，此时一个 $S_{i,j}$ 内部的任意两点距离 $\le \dfrac{\sqrt 2}{2}r$，同时还有一个性质，对于 $S_{i,j}$，只有满足 $|i-i'|\le 2,|j-j'|\le 2$ 的 $S_{i',j'}$ 中的点有可能直接跳到 $S_{i,j}$，即以 $(i,j)$ 为中心边长 $5$ 的正方形。 证明：对于 $S_{i,j}$，如果 $|x-i'|>2$ 或 $|y-j'|>2$ 则 $S_{i,j}$ 中一点到 $S_{i',j'}$ 中一点距离至少为 $r+1$。 枚举 $S_{i,j}$，如果 $|S_{i,j}|\ge 3$ 直接判合法，否则直接暴力向其四周 $24$ 个 $S_{i',j'}$ 中所有点判断能否到达即可。 加上并查集的 $\log n$，这样做是 $O(48n\log n)$ 的。 证明：对于一个点 $(a,b)\in S_{i,j}$，只有其周围 $24$ 个 $S_{i',j'}$ 中的点可能试图与其进行合并，由于 $|S_{i',j'}|\le 2$（否则会直接判掉），因此每个点被其他点访问的总数不超过 $48$。 显然 $S_{i,j}$ 的数量是 $10^{18}$ 级别的，但是非空的数量不超过 $n$，于是把非空的 $S_{i,j}$ 离散化之后 $(i,j)$ 和编号对应关系用 map 存起来，做完了。 [Submission](https://loj.ac/s/2314437)