洛谷P3402 可持久化并查集

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=2e5+10;
 4 int rt[N],fa[N*20],mxd[N*20],ls[N*20],rs[N*20],tot,n,m;
 5 #define mid ((l+r)>>1)
 6 int cpy(int v) {int u=++tot; fa[u]=fa[v],mxd[u]=mxd[v],ls[u]=ls[v],rs[u]=rs[v]; return u;}
 7 int getfa(int x,int u,int l=1,int r=n) {
 8     if(l==r)return fa[u];
 9     return x<=mid?getfa(x,ls[u],l,mid):getfa(x,rs[u],mid+1,r);
10 }
11 void upd(int* a,int p,int x,int v,int& u,int l=1,int r=n) {
12     u=cpy(v);
13     if(l==r) {a[u]=x; return;}
14     p<=mid?upd(a,p,x,ls[v],ls[u],l,mid):upd(a,p,x,rs[v],rs[u],mid+1,r);
15 }
16 int fd(int x,int u) {
17     int fx=getfa(x,u);
18     return fx?fd(fx,u):x;
19 }
20 void mg(int x,int y,int& u) {
21     int fx=fd(x,u),fy=fd(y,u);
22     if(fx==fy)return;
23     if(mxd[fx]>mxd[fy])swap(fx,fy);
24     upd(fa,fx,fy,u,u);
25     if(mxd[fx]==mxd[fy])upd(mxd,fy,mxd[fx]+1,u,u);
26 }
27 int main() {
28     mxd[0]=1;
29     scanf("%d%d",&n,&m);
30     for(int i=1; i<=m; ++i) {
31         rt[i]=rt[i-1];
32         int f,x,y;
33         scanf("%d",&f);
34         if(f==1)scanf("%d%d",&x,&y),mg(x,y,rt[i]);
35         else if(f==2)scanf("%d",&x),rt[i]=rt[x];
36         else scanf("%d%d",&x,&y),printf("%d\n",fd(x,rt[i])==fd(y,rt[i]));
37     }
38     return 0;
39 }