总感觉到现在才来写这题有点奇怪。
并查集如果按秩合并的话，每次合并只会修改一个点的父亲。
用可持久化线段树来实现可持久化数组就行了。。
然而我写的是按子树大小合并。。结果比按秩合并慢了一点>_<
中途因为没看清楚 “回到第k次操作之后的状态” WA了好几发= =
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 const int maxn=100233; 6 const int mxnode=maxn*30; 7 int lc[mxnode],rc[mxnode],sz[mxnode],num[mxnode],fa[mxnode],rt[maxn]; 8 int i,j,k,n,m,tot,x,y; 9 10 int ra;char rx; 11 inline int read(){ 12 rx=getchar(),ra=0; 13 while(rx<'0'||rx>'9')rx=getchar(); 14 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra; 15 } 16 inline int getpos(int x){ 17 int p,a,b,mid; 18 p=rt[i-1],a=1,b=n; 19 while(a<b){ 20 mid=(a+b)>>1; 21 if(x<=mid)p=lc[p],b=mid; 22 else p=rc[p],a=mid+1; 23 } 24 return p; 25 } 26 inline void upd(int pre,int &x,int a,int b,int pos,int v){ 27 x=++tot; 28 if(a==b){num[x]=pos,fa[x]=v,sz[x]=sz[pre];return;} 29 int mid=(a+b)>>1; 30 if(pos<=mid)rc[x]=rc[pre],upd(lc[pre],lc[x],a,mid,pos,v); 31 else lc[x]=lc[pre],upd(rc[pre],rc[x],mid+1,b,pos,v); 32 } 33 inline void uni(int x,int y){ 34 for(x=getpos(x);num[x]!=fa[x];x=getpos(fa[x])); 35 for(y=getpos(y);num[y]!=fa[y];y=getpos(fa[y])); 36 if(x==y){rt[i]=rt[i-1];return;} 37 if(sz[x]<sz[y]) 38 upd(rt[i-1],rt[i],1,n,num[x],num[y]),sz[y]+=sz[x]; 39 else upd(rt[i-1],rt[i],1,n,num[y],num[x]),sz[x]+=sz[y]; 40 } 41 void build(int &x,int a,int b){ 42 x=++tot; 43 if(a==b){sz[x]=1,num[x]=fa[x]=a;return;} 44 build(lc[x],a,(a+b)>>1),build(rc[x],((a+b)>>1)+1,b); 45 } 46 47 int main(){ 48 n=read(),m=read(); 49 build(rt[0],1,n);int id; 50 for(i=1;i<=m;i++){ 51 id=read();//printf("now: %d ",now); 52 if(id==2)rt[i]=rt[read()]; 53 if(id==1)x=read(),y=read(),uni(x,y); 54 if(id==3){ 55 x=read(),y=read(); 56 for(x=getpos(x);num[x]!=fa[x];x=getpos(fa[x])); 57 for(y=getpos(y);num[y]!=fa[y];y=getpos(fa[y])); 58 printf("%d ",x==y); 59 rt[i]=rt[i-1]; 60 } 61 } 62 return 0; 63 }