Sol P12506

$n\le 1000$ 直接并查集即可。令 $i$ 表示在点 $i$ 且此时树蛙颜色为绿色，$i+n$ 表示在点 $i$ 且此时的树蛙颜色为棕色，如果原平面上 $i$ 能跳到 $j$ 则 $i$ 和 $j+n$ 合并，$j$ 和 $i+n$ 合并，显然只要最后 $i$ 和 $i+n$ 在一个集合中就是合法情况。

考虑 $n\le 10^5$。我们有以下两个结论：

把平面分成若干个 $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 存起来，做完了。