[BZOJ 3674]可持久化并查集加强版：可持久化并查集

本文主要是介绍[BZOJ 3674]可持久化并查集加强版：可持久化并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

按秩合并，即深度小的根的fa指向深度大的根；如果深度相同，那么随便合并，之后深度+1

/*
User:Small
Language:C++
Problem No.:3674
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const int M=2e5+5,N=5e6+5;
int n,m,root[M],tot,ans;
struct no{int ls,rs,fa,dep;
}a[N];
void build(int &rt,int l,int r){rt=++tot;if(l==r){a[rt].fa=l;a[rt].dep=0;return;}int mid=l+r>>1;build(a[rt].ls,l,mid);build(a[rt].rs,mid+1,r);
}
void update(int &rt,int pre,int l,int r,int pos,int val){rt=++tot;a[rt]=a[pre];if(l==r){a[rt].fa=val;return;}int mid=l+r>>1;if(pos<=mid) update(a[rt].ls,a[pre].ls,l,mid,pos,val);else update(a[rt].rs,a[pre].rs,mid+1,r,pos,val);
}
void add(int rt,int l,int r,int pos){if(l==r){a[rt].dep+=1;return;}int mid=l+r>>1;if(pos<=mid) add(a[rt].ls,l,mid,pos);else add(a[rt].rs,mid+1,r,pos);
}
int query(int rt,int l,int r,int x){if(rt==0) return 0;if(l==r) return a[rt].fa;int mid=l+r>>1;if(x<=mid) return query(a[rt].ls,l,mid,x);return query(a[rt].rs,mid+1,r,x);
}
int find(int rt,int x){int f=query(rt,1,n,x);if(x==f) return x;return find(rt,f);
}
int main(){freopen("data.in","r",stdin);//scanf("%d%d",&n,&m);build(root[0],1,n);for(int i=1;i<=m;i++){int op,x,y;scanf("%d%d",&op,&x);if(op!=2) scanf("%d",&y);x^=ans;y^=ans;root[i]=root[i-1];if(op==1){x=find(root[i],x),y=find(root[i],y);if(x==y) continue;if(a[x].dep>a[y].dep) swap(x,y);update(root[i],root[i-1],1,n,x,y);if(a[x].dep==a[y].dep) add(root[i],1,n,y);}else if(op==2) root[i]=root[x];else{x=find(root[i],x),y=find(root[i],y);printf("%d\n",(x==y));}}return 0;
}