/* bzoj 3674: 可持久化并查集加强版 http://www.lydsy.com/JudgeOnline/problem.php?id=3674 用可持久化线段树维护可持久化数组从而实现可持久化并查集 可持久化线段树+并查集+路径压缩+读入优化 */ #include <cstdio> #include <algorithm> using namespace std; const int Nmax=200005; int root_fa[Nmax]; inline int read() { int x=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } struct Node { int ls; int rs; int data; }; Node fa[40*Nmax]; int n,m,ans,a,b,k; int size_fa; void build_fa(int &root,int l,int r) { root=size_fa++; int mid=(l+r)>>1; if(l==r) { fa[root].data=l; return; } build_fa(fa[root].ls,l,mid); build_fa(fa[root].rs,mid+1,r); } void insert_fa(int last,int &root,int pos,int data,int l,int r) { fa[size_fa]=fa[last]; root=size_fa; size_fa++; if(fa[root].ls==fa[root].rs) { // printf("root:%d,l:%d,data:%d\n",root,fa[root].l,data); fa[root].data=data; return; } int mid=(l+r)>>1; if(pos<=mid) insert_fa(fa[last].ls,fa[root].ls,pos,data,l,mid); else insert_fa(fa[last].rs,fa[root].rs,pos,data,mid+1,r); } int search_fa(int root,int pos,int l,int r) { if(fa[root].ls==fa[root].rs) return fa[root].data; int mid=(l+r)>>1; if(pos<=mid) return search_fa(fa[root].ls,pos,l,mid); else return search_fa(fa[root].rs,pos,mid+1,r); } int find(int i,int x) { // if(x==0) // printf("error!!!!\n"); int fa=search_fa(root_fa[i],x,1,n); if(fa==x) return fa; int t=find(i,fa); insert_fa(root_fa[i],root_fa[i],fa,t,1,n); return t; } void watch(int root,int l,int r) { if(l==r) { printf("fa[%d]=%d\n",l,fa[root].data); return; } int mid=(l+r)>>1; watch(fa[root].ls,l,mid); watch(fa[root].rs,mid+1,r); } int main() { // freopen("bzoj3674.in","r",stdin); //scanf("%d%d",&n,&m); n=read(); m=read(); ans=0; int q; build_fa(root_fa[0],1,n); // printf("the 0 watch:\n"); // watch(root_fa[0],1,n); for(int i=1;i<=m;i++) { //scanf("%d",&q); q=read(); if(q==1) { a=read(); b=read(); // scanf("%d%d",&a,&b); a^=ans;b^=ans; int rt1=find(i-1,a),rt2=find(i-1,b); // printf("root[%d]=%d,root[%d]=%d\n",a,rt1,b,rt2); if(rt1==rt2) root_fa[i]=root_fa[i-1]; else insert_fa(root_fa[i-1],root_fa[i],rt1,rt2,1,n); // printf("search_fa[2]=%d\n",search_fa(root_fa[1],2) ); // printf("root[%d]=%d,root[%d]=%d\n",a,find(root_fa[i],a),b,find(root_fa[i],b)); } else if(q==2) { k=read(); // scanf("%d",&k); k^=ans; root_fa[i]=root_fa[k]; } else if(q==3) { a=read(); b=read(); // scanf("%d%d",&a,&b); root_fa[i]=root_fa[i-1]; a^=ans; b^=ans; if(find(i,a)==find(i,b)) ans=1; else ans=0; printf("%d\n",ans); } //insert_fa(root_fa[i-1],root_fa[i],2,3); // printf("root_fa[%d]:%d\n",i,root_fa[i]); // printf("the %d watch:\n",i); // watch(root_fa[i],1,n); } return 0; }