符号约定

下文固定一个正整数 nn，定义全集 U={1,2,…,n}U=\{1,2,\dots,n\}。

并查集用一个父亲函数 p:U→Up:U\to U 表示，初始化 ∀x∈U,p(x)=x\forall x\in U,p(x)=x。

称一个父亲函数 pp 是合法的，当且仅当对任意 x∈Ux\in U，不断应用 pp：x, p(x), p(p(x)),…x,\ p(x),\ p(p(x)),\dots 最终一定会到达某个点 rr，并且这个点满足 r=p(r)r=p(r)，这个 rr 就叫做 xx 在父亲函数 pp 下的根，记为 root⁡p(x)\operatorname{root}_p(x)。

一个集合划分 P\mathcal P 指 UU 的若干个非空子集，它们两两不交，且并集为 UU。

对合法的 pp，划分 Pp\mathcal P_p 定义为 \{ \[r\] \mid r\in U,r=p(r)\}，其中 \[r\]=\{x\in U\mid p(x) = r\}

路径压缩

求 root⁡p(x)\operatorname{root}_p(x) 的函数 find⁡(x)\operatorname{find}(x) 的操作过程如下：

  1. 若 p(x)=xp(x)=x，返回 xx；
  2. 若 p(x)≠xp(x)\neq x，先递归求出 r=find⁡(p(x))r=\operatorname{find}(p(x))，再令 p(x)←rp(x)\gets r，并返回 rr。

假设 xx 到根路径为 v1,v2,…,vkv_1,v_2,\dots,v_k，其中 vkv_k 是根，那么本次操作就是 ∀i, 1≤i<k, p(vi)←vk\forall i,\ 1\le i<k,\ p(v_i)\gets v_k。

下证设进行操作前父亲函数 pp 是合法的，那么进行一次操作之后父亲函数 p′p' 也是合法的，并且 ∀y∈U, root⁡p′(y)=root⁡p(y)\forall y\in U,\ \operatorname{root}_{p'}(y)=\operatorname{root}_p(y)。

证明：

任取一个 y∈Uy\in U：

  • 如果从 yy 出发不断应用 pp 的过程中没有经过 v1,v2,…,vk−1v_1,v_2,\dots,v_{k-1}，那么 yy 在 pp 下走过的路径与在 p′p' 下相同，因此仍到达同一个根；
  • 否则设从 yy 出发在 pp 下第一次经过的被修改点是 viv_i，则在 p′p' 下到达 viv_i 后下一步直接到达 vkv_k，此时 root⁡p′(y)=root⁡p(y)=vk\operatorname{root}_{p'}(y)=\operatorname{root}_p(y)=v_k，并且 p(vk)=p′(vk)=vkp(v_k)=p'(v_k)=v_k。

集合合并

合并 x,yx,y 所在集合的函数 merge⁡(x,y)\operatorname{merge}(x,y) 的操作过程如下：

  1. 求 rx=find⁡(x)r_x=\operatorname{find}(x) 且 ry=find⁡(y)r_y=\operatorname{find}(y)；
  2. 若 rx=ryr_x=r_y，不做更改，否则令 p(rx)p(r_x) 修改为 ryr_y。

设执行了两次 find⁡\operatorname{find} 之后，修改 p(rx)p(r_x) 为 ryr_y 前的父亲函数是 pp，修改后的父亲函数是 p′p'，那么

  • 满足 root⁡p(u)=rx\operatorname{root}_p(u)=r_x 的 uu 满足 root⁡p′(u)=ry\operatorname{root}_{p'}(u)=r_y；

  • 满足 root⁡p(u)=ry\operatorname{root}_p(u)=r_y 的 uu 满足 root⁡p′(u)=ry\operatorname{root}_{p'}(u)=r_y；

  • 满足 root⁡p(u)∉{rx,ry}\operatorname{root}_p(u)\notin\{r_x,r_y\} 的 uu 满足 root⁡p′(u)=root⁡p(u)\operatorname{root}_{p'}(u)=\operatorname{root}_p(u)。

若 rx=ryr_x=r_y，则 p′=pp'=p，显然合法；否则 rx,ryr_x,r_y 是两个不同的根，令 rxr_x 指向 ryr_y 后所有点都能找到一个根，所以 p′p' 仍然是合法的。

DSU-NEXT

下面介绍一个常用的 trick，用来处理对一个固定的 nn，每次处理 l∼rl\sim r 中的所有点，但是每一个点只需要被处理一次，如将初始全 00 的序列区间修改为 11。

定义带哨兵的全集 I={1,2,…,n+1}I=\{1,2,\dots,n+1\}，其中 n+1n+1 永远不会被删除，维护一个存活集合 S⊆IS\subseteq I，初始为 S=IS=I。

支持对这个集合 SS 进行如下两种操作：

  1. 对 x∈S,x≠n+1x\in S,x\neq n+1，令 S←S∖{x}S\gets S\setminus \{x\}
  2. 在 SS 中查询 ≥i\ge i 的最小的数，记为 N(i)N(i)，这里不要求 i∈Si\in S，只要求 i∈Ii\in I。

因为 n+1∈Sn+1\in S 永远成立，所以 N(i)N(i) 总是良定的。

我们可以用并查集维护这个集合，具体地讲，初始时 ∀x∈I,p(x)=x\forall x\in I,p(x)=x，那么：

  1. 删除操作实现起来即 p(x)←root⁡p(x+1)p(x)\gets \operatorname{root}_p(x+1)；
  2. 查询操作就是返回 root⁡p(i)\operatorname{root}_p(i)。

我们来证明任意时刻都有 root⁡p(i)=N(i)\operatorname{root}_p(i)=N(i)。

对删除次数进行归纳，没删除时显然成立，假设某次删除前集合为 SS，删除了 xx，分 x−1,x+1x-1,x+1 分别是否存活四种情况画个图讨论即可。