似乎好久没有写博客了，其实写了一个EC-final游记，但是不太想发

今天来挖个坟，这是一年前我发的帖子关于并查集随机合并复杂度正确性，当时帖子底下有许多或对或错的感性证明。

在写带撤销并查集的时候，因为路径压缩只能保证均摊复杂度。所以往往需要写按秩合并，而这种随机合并的写法可以让你省去几秒钟的思考，省去几行代码，减少一点数组操作~~，增加一些常数。~~

今天又写了一个带撤销并查集的题，用到了这个写法。又想了想这种合并方法，似乎可以严谨证明，就写一下，以后可以放心这么写不被卡了。

注意：下文的证明基于以下这种先find再比较rnd的写法！别的写法可能被卡，详见上面帖子中我的回复

1
2
3
4
5
6
7

int find(int x){return fa[x]==x?x:find(fa[x]);}
void mrg(int x,int y){
    x=find(x),y=find(y);
    if(rnd[x]>rnd[y])swap(x,y);//其中 rnd[i] 是预处理的随机数
    hist.push({y,fa[y]});
    fa[y]=x;
}

定理. 上述这种写法中，无论以什么样的顺序合并，一个大小为 $n$ 的集合的期望高度是 $O(\log n)$。

证明.

不妨定义一棵树的指数高度为 $h=2^{d}$，其中 $d$ 是这棵树原本的高度。

记 $f(n)$ 为一个大小为 $n$ 的集合，其指数高度的期望。记 $g(n)$ 为一个大小为 $n$ 的集合，其高度的期望。

假设目前合并两个大小分别为 $n,m$ 的集合，他们的深度分别为 $d_n,d_m$。

如果合并时以 $n$ 为根，则合并后树的高度为：

以 $m$ 为根同理。

引理. 以大小为 $n$ 的集合的根为根的概率为 $n\over n+m$。

证明. 等价于 $n+m$ 个 rnd 值中，最大值是属于其中特定 $n$ 个点的概率，显然得证。

因此，可以得到：$E(h)\le \frac{n(h_n+2h_m)}{n+m}+\frac{m(2h_n+h_m)}{n+m}$

引理. $\forall x,f(x)\le x^2$

证明. 想证明 $f(t)\le t^2$，只需要证明对于任意 $n,m(n+m=t)$，如果最后一次合并的集合大小分别为 $n,m$，都有 $E(h)\le t^2$。不妨归纳证明

若已知 $f(n)\le n^2,f(m)\le m^2$，则带入上式得证：

根据琴升不等式：

因此：