总感觉到现在才来写这题有点奇怪。

　　并查集如果按秩合并的话，每次合并只会修改一个点的父亲。

　　用可持久化线段树来实现可持久化数组就行了。。

　　然而我写的是按子树大小合并。。结果比按秩合并慢了一点>_<

　　中途因为没看清楚 “回到第k次操作之后的状态” WA了好几发= =

1 #include
      
        2 #include
       
         3 #include
        
          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
         
          >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]
          
           >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\n",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\n",x==y);59             rt[i]=rt[i-1];60         }61     }62     return 0;63 }