HYSBZ 3673 可持久化并查集 by zky

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int ch[maxn][2],val[maxn];
int tot,rootfa[maxn],rootdep[maxn];
void build(int &now,int l,int r){
    now=++tot;
    if(l==r){
        val[now]=l;
        return ;
    }
    int mid=l+r>>1;
    build(ch[now][0],l,mid);
    build(ch[now][1],mid+1,r);
}
void modify(int old,int &now,int l,int r,int pos,int v){
    now=++tot;
    if(l==r){
        val[now]=v;
        return;
    }
    ch[now][0]=ch[old][0];
    ch[now][1]=ch[old][1];
    int mid=l+r>>1;
    if(pos<=mid) modify(ch[old][0],ch[now][0],l,mid,pos,v);
    else modify(ch[old][1],ch[now][1],mid+1,r,pos,v);
}
int query(int now,int l,int r,int pos){
    if(l==r) return val[now];
    int mid=l+r>>1;
    if(pos<=mid) return query(ch[now][0],l,mid,pos);
    else return query(ch[now][1],mid+1,r,pos);
}
int n,m,a,b,k;
int find(int now,int x){
    int fx=query(rootfa[now],1,n,x);
    return fx==x?x:find(now,fx);
}
void merge(int now,int x,int y){
    x=find(now-1,x),y=find(now-1,y);
    if(x==y){
        rootdep[now]=rootdep[now-1];
        rootfa[now]=rootfa[now-1];
        return ;
    }
    int dx=query(rootdep[now-1],1,n,x);
    int dy=query(rootdep[now-1],1,n,y);
    if(dx<dy){
        modify(rootfa[now-1],rootfa[now],1,n,x,y);
        rootdep[now]=rootdep[now-1];
    }else if(dx>dy){
        modify(rootfa[now-1],rootfa[now],1,n,y,x);
        rootdep[now]=rootdep[now-1];
    }else{
        modify(rootfa[now-1],rootfa[now],1,n,x,y);
        modify(rootdep[now-1],rootdep[now],1,n,y,dy+1);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    build(rootfa[0],1,n);
    for(int i=1;i<=m;i++){
        int opt;scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d",&a,&b);
            merge(i,a,b);
        }else if(opt==2){
            scanf("%d",&k);
            rootdep[i]=rootdep[k];
            rootfa[i]=rootfa[k];
        }else{
            scanf("%d%d",&a,&b);
            rootdep[i]=rootdep[i-1];
            rootfa[i]=rootfa[i-1];
            ///cout<<find(1,a)<<endl;
            a=find(i,a),b=find(i,b);
            printf("%d\n",(a==b));
        }
    }
    return 0;
}