欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HYSBZ 3673 可持久化并查集 by zky

程序员文章站 2024-03-03 17:53:22
...
#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;
}