Description
n个集合 m个操作 操作： 1 a b 合并a,b所在集合 2 k 回到第k次操作之后的状态(查询算作操作) 3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
0<n,m<=2*10^4
Input
Output
Sample Input
5 6 1 1 2 3 1 2 2 0 3 1 2 2 1 3 1 2
Sample Output
1 0 1
Solution
板子题……只不过网上有很多假做法。
具体做法就是整两个可持久化数组（不知道谁起的这么鬼畜的名字……我还是更喜欢叫他可持久化线段树）来记录并查集的$fa$数组和$dep$数组。因为路径压缩会破坏可持久化的结构，所以我们只能记录$dep$数组来按秩合并。
网上很多只搞了一颗可持久化线段树，维护$fa$就可持久化线段树$insert$一条链，维护$dep$就修改历史版本上的点的做法是错的……已经被卡掉了QAQ
Code
1 #include2 #include 3 #define N (200009) 4 using namespace std; 5 6 int n,m,lastans,opt,x,y; 7 8 struct Tree 9 {10 struct Sgt{ int ls,rs,v;}Segt[N*20];11 int sgt_num,a[N],Root[N];12 int Build(int l,int r)13 {14 int now=++sgt_num;15 if (l==r) {Segt[now].v=a[l]; return now;}16 int mid=(l+r)>>1;17 Segt[now].ls=Build(l,mid);18 Segt[now].rs=Build(mid+1,r);19 return now;20 }21 int Update(int pre,int l,int r,int x,int v)22 {23 int now=++sgt_num;24 Segt[now].ls=Segt[pre].ls;25 Segt[now].rs=Segt[pre].rs;26 if (l==r) {Segt[now].v=v; return now;}27 int mid=(l+r)>>1;28 if (x<=mid) Segt[now].ls=Update(Segt[now].ls,l,mid,x,v);29 else Segt[now].rs=Update(Segt[now].rs,mid+1,r,x,v);30 return now;31 }32 int Query(int now,int l,int r,int x)33 {34 if (l==r) return Segt[now].v;35 int mid=(l+r)>>1;36 if (x<=mid) return Query(Segt[now].ls,l,mid,x);37 else return Query(Segt[now].rs,mid+1,r,x);38 }39 }CT[2];40 41 int Find(int x,int t)42 {43 int fa=CT[0].Query(CT[0].Root[t],1,n,x);44 return x==fa?x:Find(fa,t);45 }46 47 int main()48 {49 scanf("%d%d",&n,&m);50 for (int i=1; i<=n; ++i)51 CT[0].a[i]=i, CT[1].a[i]=1;52 CT[0].Root[0]=CT[0].Build(1,n);53 CT[1].Root[0]=CT[1].Build(1,n);54 for (int i=1; i<=m; ++i)55 {56 scanf("%d",&opt);57 if (opt==1)58 {59 CT[0].Root[i]=CT[0].Root[i-1];60 CT[1].Root[i]=CT[1].Root[i-1];61 scanf("%d%d",&x,&y);62 /*x^=lastans; y^=lastans;*/63 int fx=Find(x,i),fy=Find(y,i);64 if (fx==fy) continue;65 int dfx=CT[1].Query(CT[1].Root[i],1,n,fx);66 int dfy=CT[1].Query(CT[1].Root[i],1,n,fy);67 if (dfx>dfy) swap(fx,fy);68 CT[0].Root[i]=CT[0].Update(CT[0].Root[i],1,n,fx,fy);69 if (dfx!=dfy) continue;70 CT[1].Root[i]=CT[1].Update(CT[1].Root[i],1,n,fy,dfy+1);71 }72 if (opt==2)73 {74 scanf("%d",&x); /*x^=lastans;*/75 CT[0].Root[i]=CT[0].Root[x];76 CT[1].Root[i]=CT[1].Root[x];77 }78 if (opt==3)79 {80 CT[0].Root[i]=CT[0].Root[i-1];81 CT[1].Root[i]=CT[1].Root[i-1];82 scanf("%d%d",&x,&y);83 /*x^=lastans; y^=lastans;*/84 int fx=Find(x,i),fy=Find(y,i);85 if (fx==fy) puts("1")/*, lastans=1*/;86 else puts("0")/*, lastans=0*/;87 }88 }89 }