可持久化并查集

更新日志

2025/07/29：开工。

---

前言

我竟然没会可持久化并查集。

实现

可持久化平衡树维护一下父节点数组，与按秩合并的秩数组即可。

模板题

LG3402

code

const int N=1e5+5,M=2e5+5;int n,m;struct perseg{int cnt;int rt[M];int ls[N<<6],rs[N<<6],dat[N<<6];void build(int a[],int &x,int l=1,int r=n){if(!x)x=++cnt;if(l==r)return dat[x]=a[l],void();int m=l+r>>1;build(a,ls[x],l,m);build(a,rs[x],m+1,r);}void copy(int x,int y){dat[y]=dat[x],ls[y]=ls[x],rs[y]=rs[x];}void change(int k,int v,int x,int &y,int l=1,int r=n){copy(x,y=++cnt);if(l==r)return dat[y]=v,void();int m=l+r>>1;if(k<=m)change(k,v,ls[x],ls[y],l,m);else change(k,v,rs[x],rs[y],m+1,r);}int query(int k,int x,int l=1,int r=n){if(l==r)return dat[x];int m=l+r>>1;if(k<=m)return query(k,ls[x],l,m);else return query(k,rs[x],m+1,r);}
}fa,rk;int v;
int find(int x){int f;while((f=fa.query(x,fa.rt[v]))!=x)x=f;return x;}
void merge(int a,int b){a=find(a),b=find(b);int rka=rk.query(a,rk.rt[v]),rkb=rk.query(b,rk.rt[v]);if(rka>rkb)swap(a,b),swap(rka,rkb);fa.change(a,b,fa.rt[v],fa.rt[v+1]);if(rka==rkb)rk.change(b,rkb+1,rk.rt[v],rk.rt[v+1]);else rk.rt[v+1]=rk.rt[v];++v;
}
bool same(int a,int b){return find(a)==find(b);}int Fa[N],Rk[N];
inline void Main(){read(n,m);rep(i,1,n)Fa[i]=i,Rk[i]=1;fa.build(Fa,fa.rt[0]);rk.build(Rk,rk.rt[0]);rep(i,1,m){int op;read(op);if(op==1){int a,b;read(a,b);merge(a,b);}else if(op==2){int k;read(k);++v;fa.rt[v]=fa.rt[k];rk.rt[v]=rk.rt[k];}else{int a,b;read(a,b);put(same(a,b));++v;fa.rt[v]=fa.rt[v-1];rk.rt[v]=rk.rt[v-1];}}
}