记录编号	250568	评测结果	AAAAAAAAAA
题目名称	[BZOJ 3674] 可持久化并查集加强版	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.670 s
提交时间	2016-04-15 12:10:02	内存使用	87.27 MiB

#define MAXN 600010UL

#include <cstdio>

int n,m,Ans;

struct ChairManTree{
	int ls[MAXN*6],rs[MAXN*6],val[MAXN*6],cnt,root[MAXN];
	inline void Build(int &rt,int l,int r){
		rt=++cnt;
		if(l==r){val[rt]=l;return;}
		int mid=(l+r)>>1;
		Build(ls[rt],l,mid);
		Build(rs[rt],mid+1,r);
		return;
	}
	inline void Modify(int rpt,int &rt,int pos,int l,int r,int new_val){
		rt=++cnt;
		if(l==r){val[rt]=new_val;return;}
		int mid=(l+r)>>1;
		if(pos<=mid) rs[rt]=rs[rpt],Modify(ls[rpt],ls[rt],pos,l,mid,new_val);
		else ls[rt]=ls[rpt],Modify(rs[rpt],rs[rt],pos,mid+1,r,new_val);
		return;
	}
	inline void Add(int id,int pos,int new_val){
		Modify(root[id-1],root[id],pos,1,n,new_val);
		return;
	}
	inline void InBuild(){
		Build(root[0],1,n);
		return;
	}
	inline int Query(int rt,int pos,int l,int r){
		if(l==r) return val[rt];
		int mid=(l+r)>>1;
		if(pos<=mid) return Query(ls[rt],pos,l,mid);
		else return Query(rs[rt],pos,mid+1,r);
	}
	inline int Q(int id,int x){
		return Query(root[id],x,1,n);
	}
	inline void SetRoot(int p1,int p2){
		root[p1]=root[p2];
		return;
	}
};

ChairManTree tree,depth;

inline int in(){
	int x=0,c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x;
}

int getf(int id,int p){
	int k=tree.Q(id,p);
	if(k==p) return k;
	return getf(id,k);
}

inline int Qdp(int id,int p){
	return depth.Q(id,p);
}

int main(){
	freopen("bzoj_3974.in","r",stdin);
	freopen("bzoj_3974.out","w",stdout);
	n=in(),m=in();
	tree.InBuild();
	for(int i=1,a,b,op,d1,d2;i<=m;i++){
		op=in();
		if(op==1){
			a=getf(i-1,in()^Ans),b=getf(i-1,in()^Ans);
			if(a==b){
				tree.SetRoot(i,i-1);
				depth.SetRoot(i,i-1);
				continue;
			}
			d1=Qdp(i-1,a),d2=Qdp(i-1,b);
			if(d1==d2){
				depth.Add(i,b,d1+1);
			}
			else{
				if(d1>d2) a^=b,b^=a,a^=b;
				depth.SetRoot(i,i-1);
			}
			tree.Add(i,a,b);
		}
		else if(op==2) a=in()^Ans,tree.SetRoot(i,a),depth.SetRoot(i,a);
		else{
			tree.SetRoot(i,i-1);
			depth.SetRoot(i,i-1);
			a=getf(i,in()^Ans),b=getf(i,in()^Ans);
			printf("%d\n",Ans=(a==b));
		}
	}
	return 0;
}