算法

维护连通块

现有一棵 $n$ 个节点的树。我们构建一最小的连通块 $S(l,r)$，包含编号在 $[l,r]$ 中的所有节点。多次询问，每次对于任意一对 $[l,r]$，询问关于这连通块的信息。

如果可以离线/可持久化，此类问题有一通用思路：用扫描线维护“$r$ 固定时不同 $l$ 构成连通块的信息”。若 $[p,q]\subseteq[l,r]$，则 $S(l,r)\supseteq S(p,q)$；对于一固定的 $r$，我们维护 $l$ 分别取 $r,r-1,\cdots,1$（向左拓展）时，连通块的增量。对于点 $x$，我们记录 $t_r(x)$ 表示 $r$ 固定时使得 $x\in S(l,r)$ 的最大的 $l$。假设已经对于 $r$ 维护好了；现在拓展到 $r’=r+1$。

若 $x\notin \{r,r+1\}$，则 $t_{r+1}(x)\neq t_{r}(x)$ 是

• $x$ 在 $r$ 到 $r+1$ 的简单路径上，且
• $t_{r+1}(x)=r$

的充分必要条件。

考虑任意 $l$。由于 $S$ 是极小的，故将 $r+1$“加入”$S(l,r)$ 得到 $S(l,r+1)$，只需找到 $r+1$ 和连通块在树上最接近节点之间的路径，将路径上所有点加入连通块；由树的性质，此路径是通向 $[l,r]$ 中任意节点的必经之路，也即 $r,r+1$ 的最短路径的某一前缀。又当 $l=r$ 时，$S(l,r+1)$ 就是该路径本身；再有 $[p,q]\subseteq[l,r]\Longrightarrow S(l,r)\supseteq S(p,q)$，故本命题得证。

因此，我们需将整条路径上的点的最大出现时间整体覆盖成 $t_{r+1}(x)=r$（$r+1$ 本身除外，它是 $t_{r+1}(r+1)=r+1$）。可以使用珂朵莉树和树剖维护连续的 $t(x)$ 相同的一段。设 $Φ$ 表示连续段个数。每次覆盖操作会对 $\newcommand\bigO{\operatorname{O}}\bigO(\log n)$ 条重链执行“删除若干连续段，加入 $\bigO(1)$ 个连续段”的操作。又 $Φ\leq n$，则 $Φ$ 的总变化量是 $\bigO(n\log n)$ 的。因此若用对数级别有序关联式容器（如 std::map），总时间复杂度为 $\bigO(n\log^2 n)$。 （更多…）