并查集的应用

A

加边，维护连通性

使用路径压缩，时间复杂度$O(n\log_2n)$。

使用按秩合并，时间复杂度$O(n\log_2n)$。

两个都用，时间复杂度$O(n\alpha(n))$。

B

加边，撤消上次加边，维护连通性

使用按秩合并，记录上次加的边对应的树边。这样在撤消的时候是$O(1)$的。

时间复杂度$O(n\log_2n)$。

可撤消并查集：

struct dsu{
    int f[M],g[M];
    void init(int n){ FOR(i,0,n)f[i]=i,g[i]=1; }
    dsu(){}
    dsu(int n){init(n);}
    typedef pair<pair<int*,int>,int> ppi;//f[],val,time
    stack<ppi> s;
    int current_time(){ return s.empty()?0:s.top().se; }
    int get(int u){ return f[u]==u?u:get(f[u]); }
    bool find(int u,int v){ return get(u)==get(v); }

    void merge(int u,int v){
        int cur=current_time()+1;
        u=get(u),v=get(v);
        if(u==v)return;
        if(g[u]==g[v]){
            s.push(mk(mk(f+u,f[u]),cur)), f[u]=v;
            s.push(mk(mk(g+v,g[v]),cur)), g[v]++;
        } else {
            if(g[u]>g[v])swap(u,v);
            s.push(mk(mk(f+u,f[u]),cur)), f[u]=v;
        }
    }
    void undo(){
        int cur=current_time();
        while(current_time()==cur){
            ppi u=s.top();s.pop();
            *u.fi.fi = u.fi.se;
        }
    }
    void undo(int untiltime){
        while(current_time()>untiltime)undo();
    }
};

C

支持加边，询问

$$\sum_{i=1}^n\sum_{j=i+1}^nL(i,j)$$

$L(i,j)$表示$i$和$j$最早在什么时候连通。

维护每个连通块的大小，加边的时候统计一下即可。

时间复杂度$O(n\alpha(n))$。

D

支持加边，求两个点在什么时候连通。

路径权值为它被添加的时间，显然可以建树，倍增求路径最小值。时间复杂度$O(n\log_2n)$。

E

支持加边，询问第$x$个点在第$i$时刻所在连通块的大小。

显然可以离线，按时刻排序后可以顺着做一遍。

还有一个在线的思路，就是每一条边的权值为它的出现时间，那么建一个 kruskal 重构树（就是在加边的时候新建虚点）。然后每个子树记录它非虚点的个数。显然，祖先路径上边的权值显然是从下到上递增的。这样问题就转化为求祖先路径上第一个权值大于$t$的边对应的结点，倍增搞一下就行。

F

给一个数组$\left\langle a_i \right\rangle_{i=1}^n$，一开始全是$0$，每次两种操作：

1. 令$a_x=1$；
2. 输出$\left\langle a_i \right\rangle_{i=x}^n$中第一个$0$的位置。

建立一个并查集，指向它右边第一个$0$的位置。初始时都指向自己。赋值相当于$f_x=get(x+1)$。

G

给一个数组$\left\langle a_i \right\rangle_{i=1}^n$, 一开始全是$0$, 每次操作会将$\left\langle a_i \right\rangle_{i=l}^r$中还是$0$的全部变成$k$。
求最后的数组⻓什么样。

仍然是并查集指向下一个$0$的位置，直接暴力改就行，均摊并查集复杂度。

H

一个序列，支持区间开根，区间求和。

并查集指向右边第一个大于$1$的数，然后暴力改就行。

均摊复杂度$O(n\log_2n\alpha(n))$。

I

给定$\left\langle a_i \right\rangle_{i=1}^n,\left\langle b_i \right\rangle_{i=1}^n,\left\langle c_i \right\rangle_{i=1}^n$，求$a_ib_j\min_{k=i}^jc_k$的最大值。

把$c_i$按照从大到小排序，每次加入一个点，连接两边相邻点所在连通块。显然可以每个连通块维护$a_i,b_i$的最大值，然后在合并的时候更新答案。有一些细节需要考虑。

复杂度$O(n\log_2n)$。

J

给定一棵树，每次加边或者询问两个点之间是否有至少两条边不相交的路径。

即询问两个点是否在一个环上。手玩一下可以发现，每添加一条边相当于覆盖一条路径，当两个覆盖有重叠部分时它们就“连通”了，两个路径上的点都可以互达。于是就可以并查集，每次指向祖先路径上还没被覆盖的点。每个点记一个深度，然后就可以愉快并查集了。