自动搬运

查看原文

来自洛谷，原作者为

	juju527 **

搬运于2025-08-24 22:26:53，当前版本为作者最后更新于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$。

$suf_i$ 表示满足 $j>i\And b_j<b_i\And \text{dist}(i,j)\leq C$ 的最小的 $j$。

显然，点 $i$ 在区间 $[l,r]$ 的情况下是代表元当且仅当 $pre_i<l\And suf_i>r\And l\leq i\leq r$。

求出 $pre,suf$ 后这个问题显然可以用离线扫描线解决。

考虑如何求出 $pre,suf$。

由于 $\text{dist}$ 的奇怪限制，我们考虑点分治。

值得一提的是点分治的过程中，由于我们只需要求一个最优化的式子，甚至不用管不同子树的限制。

建立一颗以标号排序的平衡树，记录区间最小的到重心的距离。

将整个块按 $b_i$ 从小到大的顺序插入平衡树里，依次询问即可。

总的时间复杂度 $O(n\log^2n+m\log n)$。

code