记录编号	529139	评测结果	AAAAAAAAAA
题目名称	[BZOJ 3674] 可持久化并查集加强版	最终得分	100
用户昵称	LGLJ	是否通过	通过
代码语言	C++	运行时间	0.654 s
提交时间	2019-03-28 15:08:22	内存使用	38.98 MiB

#include <iostream>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#define I inline
#define R register
using namespace std;
const int maxn=2*1e5+10;
int n,m;
struct TREE
{
	int l,r,fa,deep;
}tree[maxn*20];
int zxt[maxn]={0},tot=0;
int lastans=0;
I int read()
{
	int x=0;
	char ch=0;
	bool w=true;
	while(!isdigit(ch)){if(ch=='-')w=false;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return w?x:-x;
}
I void build(int &rt,int le,int ri)
{
	rt=++tot;
	if(le==ri)
	{
		tree[rt].fa=le;
		tree[rt].deep=1;
		return ;
	}
	int mid=(le+ri)>>1;
	build(tree[rt].l,le,mid);
	build(tree[rt].r,mid+1,ri);
}
I void join(int &rt,int le,int ri,int pre,int x,int y)
{
	rt=++tot;
	tree[rt].l=tree[pre].l;
	tree[rt].r=tree[pre].r;//只有叶子节点对应的是各个集合，其他点的fa,deep没必要更新
	if(le==ri)
	{
		tree[rt].fa=y;
		tree[rt].deep=tree[pre].deep;
		return ;
	}
	int mid=(le+ri)>>1;
	if(x<=mid)
		join(tree[rt].l,le,mid,tree[pre].l,x,y);
	else
		join(tree[rt].r,mid+1,ri,tree[pre].r,x,y);
}
I void update(int rt,int le,int ri,int x)
{
	if(le==ri)
	{
		++tree[rt].deep;
		return ;
	}
	int mid=(le+ri)>>1;
	if(x<=mid)
		update(tree[rt].l,le,mid,x);
	else
		update(tree[rt].r,mid+1,ri,x);
}
I int query(int rt,int le,int ri,int x)//返回主席树中的位置
{
	if(le==ri)
		return rt;//找到x在主席树中对应的位置
	int mid=(le+ri)>>1;
	if(x<=mid)
		return query(tree[rt].l,le,mid,x);
	else
		return query(tree[rt].r,mid+1,ri,x);
}
I int find(int rt,int x)
{
	int now=query(rt,1,n,x);//找到主席树中对应的那个点所在位置
	return tree[now].fa==x?now:find(rt,tree[now].fa);
}
I int MAIN()
{
	freopen ("bzoj_3974.in","r",stdin);
	freopen ("bzoj_3974.out","w",stdout);
	n=read(),m=read();
	build(zxt[0],1,n);
	for(R int i=1,a,b,c;i<=m;++i)
	{
		a=read(),b=read();
		switch(a)
		{
			case 1:
			{
				c=read();
				b^=lastans,c^=lastans;
				zxt[i]=zxt[i-1];//先将整个树平移过来
				int x=find(zxt[i],b),y=find(zxt[i],c);
				if(tree[x].fa!=tree[y].fa)//判断是否就在一个集合里
				{
					if(tree[x].deep>tree[y].deep)//x的深度要<y
						swap(x,y);
					join(zxt[i],1,n,zxt[i-1],tree[x].fa,tree[y].fa);//合并
					if(tree[x].deep==tree[y].deep)
						update(zxt[i],1,n,tree[y].fa);
				}
				break;
			}
			case 2:
			{
				b^=lastans;
				zxt[i]=zxt[b];//回到原先状态
				break;
			}
			default:
			{
				c=read();
				b^=lastans,c^=lastans;
				zxt[i]=zxt[i-1];
				int x=find(zxt[i],b),y=find(zxt[i],c);
				if(tree[x].fa==tree[y].fa)
					lastans=1;
				else
					lastans=0;
				printf("%d\n",lastans);
			}
		}
	}
	return 0;
}
int lglj=MAIN();
int main(){;}