题解 P7126 [Ynoi2008] rdCcot

juju527 · 2021-08-19 17:42:13 · 题解

前置知识

点分治，平衡树，扫描线。

\texttt{Solution}

对于数图的连通块的题目，

如果图是森林，最常见的方法是“点数减边数”。

对于图长得很奇怪的情况，通常使用钦定“代表元”的方式数连通块。

例如：CF1548E。

由于连边的条件和距离有关，想到和深度的关系。

我们考虑用一个连通块中 bfs 序最小的点当作该连通块的代表元。

记点 i 的 bfs 序为 b_i。

这里有一个强结论：对于一个点 x，如果其与 bfs 序比其小的点无连边则其为某个连通块的代表元。

考虑证明：

引理：对于 b_i<b_j<b_k，若 \text{dist}(i,k)\leq C\And \text{dist}(j,k)\leq C，则 \text{dist(i,j)}\leq C

引理的证明可以考虑讨论下两两 \text{lca} 是否重合，容易证明。

1. 如果存在 y，满足 \text{dist}(x,y)\leq C \And b_y<b_x。

   那么显然 x 不能是代表元。

2. 如果不存在 y，满足 \text{dist}(x,y)\leq C \And b_y<b_x，且存在点 z，满足 z 与 x 在同一连通块中且 b_z<b_x。

   由于 x 不存在往前的边，但 z 与 x 在同一个 C 连通块里。

   所以存在一条路径 x\to a_1\to a_2\to\dots\to a_k\to z。

   一定存在一条 b_{a_i} 严格增的路径，根据引理容易证明。

   我们从 a_k 往前考虑。

   由于 b_z<b_{a_{k-1}}<b_{a_k}，且存在边 (z,a_k),(a_{k-1},a_k)，那么边 (z,a_{k-1}) 存在。

   通过对 k 归纳，我们最终可以得到边 (z,x) 存在。

   与命题矛盾。

故结论成立。

我们现在只需要数在区间 [l,r] 中不存在往前的边的点的个数就能得到连通块数了。

考虑记 pre_i 表示满足 j<i\And b_j<b_i\And \text{dist}(i,j)\leq C 的最大的 j。