BZOJ 3647——可持久化并查集加强版

不会可持久化并查集先去做.

幼稚的以为直接交原来的就好了，结果T了！

加个路径压缩，but一直RE，请了几位大神还是解决不了。。所以先留个坑。。

#include
     
      #include
      
       #include
       
        using namespace std;#define maxn 300050int cnt=0,ls[maxn*40],rs[maxn*40],root[maxn],sz,key[maxn*40],n,m,i,v[maxn*40];int read(){    int w=0;char c=getchar();    while(c<48||c>57) c=getchar();    while(c>=48&&c<=57){        w=w*10+c-48;        c=getchar();    }    return w;}void build(int &p,int l,int r){    p=++cnt;    if(l==r) {key[p]=l;return;}    if(l!=r){        int mid=(l+r)/2;        build(ls[p],l,mid);        build(rs[p],mid+1,r);    }}void Modify(int &p,int cmp,int l,int r,int loc,int val){    if(v[p]!=i){    p=++cnt;ls[p]=ls[cmp];rs[p]=rs[cmp];v[p]=i;}    if(l==r){        key[p]=val;    }    if(l!=r){        int mid=(l+r)>>1;        if(loc<=mid){            Modify(ls[p],ls[cmp],l,mid,loc,val);        }        else{            Modify(rs[p],rs[cmp],mid+1,r,loc,val);        }    }}inline int query(int version,int l,int r,int loc){    int mid;    while(l!=r){        mid=(l+r)>>1;        if(loc<=mid) version=ls[version],r=mid;        else version=rs[version],l=mid+1;    }    return key[version];}int find(int version,int loc){    int fa=query(root[version],1,n,loc);    if(fa==loc) return fa;    int anc=find(version,fa);    Modify(root[version],root[version],1,n,loc,anc);    return anc;}int main(){    int x,y,l,r,k,opt,lastans=0;    n=read();m=read();    build(root[0],1,n);    for(i=1;i<=m;i++){        opt=read();x=read()^lastans;        if(opt==1){            y=read()^lastans;            Modify(root[i],root[i-1],1,n,find(root[i-1],x),find(root[i-1],y));        }        else if(opt==2) root[i]=root[x];        else{            y=read()^lastans;            root[i]=root[i-1];            lastans=(find(i,x)==find(i,y));            if(lastans) printf("1\n");            else printf("0\n");        }    }    //printf("%d\n",cnt);}