记录编号	341645	评测结果	AAAAAAAAAA
题目名称	[BZOJ 3674] 可持久化并查集加强版	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.985 s
提交时间	2016-11-07 19:41:37	内存使用	196.38 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200010;
int findroot(int);
void mergeset(int,int);
void build(int,int,int&);
void modify(int,int,int&);
void query(int,int,int);
int copy(int);
int lc[maxn<<6],rc[maxn<<6],a[maxn<<6],b[maxn<<6],root[maxn],cnt=0;
int n,m,d,x,y,k,prt,size,now,ans=0;
int main(){
#define MINE
#ifdef MINE
	freopen("bzoj_3974.in","r",stdin);
	freopen("bzoj_3974.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	build(1,n,root[0]);
	for(now=1;now<=m;now++){
		scanf("%d",&d);
		if(d==1){
			scanf("%d%d",&x,&y);
			x^=ans;y^=ans;
			root[now]=copy(root[now-1]);
			mergeset(x,y);
		}
		else if(d==3){
			scanf("%d%d",&x,&y);
			x^=ans;y^=ans;
			root[now]=copy(root[now-1]);
			printf("%d\n",ans=(int)(findroot(x)==findroot(y)));
		}
		else{
			scanf("%d",&x);
			x^=ans;
			root[now]=copy(root[x]);
		}
	}
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
int findroot(int x){
	for(;;){
		k=x;
		query(1,n,root[now]);
		if(prt==x)return x;
		x=prt;
	}
	return x;
}
void mergeset(int x,int y){
	x=findroot(x);y=findroot(y);
	if(x==y)return;
	k=x;
	query(1,n,root[now]);
	int sx=size;
	k=y;
	query(1,n,root[now]);
	if(sx>size)swap(x,y);
	sx+=size;
	size=0;
	k=x;
	prt=y;
	modify(1,n,root[now]);
	k=y;
	size=sx;
	modify(1,n,root[now]);
}
void build(int l,int r,int &rt){
	rt=++cnt;
	if(l==r){
		a[rt]=l;
		b[rt]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,lc[rt]);
	build(mid+1,r,rc[rt]);
}
void modify(int l,int r,int &rt){
	rt=copy(rt);
	if(l==r){
		if(prt)a[rt]=prt;
		if(size)b[rt]=size;
		return;
	}
	int mid=(l+r)>>1;
	if(k<=mid)modify(l,mid,lc[rt]);
	else modify(mid+1,r,rc[rt]);
}
void query(int l,int r,int rt){
	if(l==r){
		prt=a[rt];
		size=b[rt];
		return;
	}
	int mid=(l+r)>>1;
	if(k<=mid)query(l,mid,lc[rt]);
	else query(mid+1,r,rc[rt]);
}
int copy(int rt){
	int x=++cnt;
	lc[x]=lc[rt];
	rc[x]=rc[rt];
	a[x]=a[rt];
	b[x]=b[rt];
	return x;
}