记录编号	364140	评测结果	AAEEEEAEEA
题目名称	[BZOJ 3674] 可持久化并查集加强版	最终得分	40
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	1.849 s
提交时间	2017-01-15 15:58:39	内存使用	1.65 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int n,m,tp,a,b,ans;
struct node{
	int key;
	node *lc,*rc;
	node(){key=0;lc=rc=0;}
};
struct array{
	node *root[N];int T;
	void init(bool tp){
		root[0]=new node();
		build(root[0],1,n,tp);
	}
	void build(node *x,int l,int r,bool tp){
		if (l==r){x->key=tp?l:1;return;}
		int mid=(l+r)>>1;
		x->lc=new node();
		x->rc=new node();
		build(x->lc,l,mid,tp);
		build(x->rc,mid+1,r,tp);
	}
	node* open(int p){//修改 
		node *x=root[T],*y=root[++T]=new node();
		int l=1,r=n;
		while (1){
			*y=*x;
			if (l==r) return y;
			int mid=(l+r)>>1;
			if (p>mid) x=x->rc,y=y->rc=new node(),l=mid+1;
				else x=x->lc,y=y->lc=new node(),r=mid;
		}
	}
	node* find(int p){//只读 
		node *x=root[T];
		int l=1,r=n;
		while (l<r){
			int mid=(l+r)>>1;
			if (p>mid) x=x->rc,l=mid+1;
				else x=x->lc,r=mid;
		}
		return x;
	}
	void go_back(int time){
		root[++T]=new node();
		*root[T]=*root[time];
	}
}fa,size;
int find(int x){
	while (1){
		node* y=fa.find(x);
		if (y->key==x) return x;
		x=y->key;
	}
}
int main()
{
	freopen("bzoj_3974.in","r",stdin);
	freopen("bzoj_3974.out","w",stdout);
	scanf("%d%d",&n,&m);
	fa.init(1);size.init(0);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&tp,&a);
		if (tp!=2) scanf("%d",&b);
		a^=ans;b^=ans;
		if (tp==1){
			a=find(a);b=find(b);
			if (a==b){
				fa.go_back(i-1);
				size.go_back(i-1);
				continue;
			}
			int sa=size.find(a)->key,sb=size.find(b)->key;
			if (sa<sb) swap(sa,sb),swap(a,b);
			node *n1=fa.open(b),*n2=size.open(a);
			n1->key=a;n2->key+=sb;
		}
		if (tp==2) fa.go_back(a),size.go_back(a);
		if (tp==3){
			printf("%d\n",ans=(find(a)==find(b)));
			fa.go_back(i-1);
			size.go_back(i-1);
		}
		/*for (int i=1;i<=n;i++) printf("%d ",fa.find(i)->key);
		puts("");*/
	}
	return 0;
}