代码

#include<bits/stdc++.h>
using namespace std;
int read()
{
	char x=getchar();int ans=0;
	while(!isdigit(x)) x=getchar();
	while(isdigit(x)) ans=ans*10+x-'0',x=getchar();
	return ans;
}
struct node
{
	int pre,ls,rs,val,sum,tag;
}tree[100005];
int stck[100005],n,m;
bool check_root(int p)
{
	return tree[tree[p].pre].ls==p||tree[tree[p].pre].rs==p;
}
void pushup(int p)
{
	tree[p].sum=tree[tree[p].ls].sum^tree[tree[p].rs].sum^tree[p].val;
}
void rev(int p)
{
	swap(tree[p].ls,tree[p].rs);
	tree[p].tag^=1;
}
void pushdown(int p)
{
	if (tree[p].tag)
	{
		rev(tree[p].ls);
		rev(tree[p].rs);
		tree[p].tag=0;
	}
}
void rotate(int x)
{
	int y=tree[x].pre,z=tree[y].pre,k=(tree[y].rs==x),w;
	if (check_root(y))
	{
		bool tmp=(tree[z].rs==y);
		if (tmp) tree[z].rs=x;
		else tree[z].ls=x;
	}
	if (k)
	{
		w=tree[x].ls;
		tree[x].ls=y;
		tree[y].rs=w;
	}
	else
	{
		w=tree[x].rs;
		tree[x].rs=y;
		tree[y].ls=w;
	}
	if (w) tree[w].pre=y;
	tree[y].pre=x;
	tree[x].pre=z;
	pushup(y);
}
void splay(int x)
{
	int y=x,top=0,z;
	stck[++top]=y;
	while(check_root(y)) stck[++top]=y=tree[y].pre;
	do
	{
		pushdown(stck[top]);
		top--;
	}
	while(top);
	while(check_root(x))
	{
		y=tree[x].pre,z=tree[y].pre;
		if (check_root(y))
		{
			if ((tree[y].ls==x)^(tree[z].ls==y)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
	pushup(x);
}
void access(int x)
{
	for (int y=0;x;y=x,x=tree[x].pre)
		splay(x),tree[x].rs=y,pushup(x);
}
void make_root(int x)
{
	access(x);
	splay(x);
	rev(x);
}
int find_root(int x)
{
	access(x);
	splay(x);
	while(tree[x].ls)
	{
		pushdown(x);
		x=tree[x].ls;
	}
	splay(x);
	return x;
}
void split(int x,int y)
{
	make_root(x);
	access(y);
	splay(y);
}
void link(int x,int y)
{
	make_root(x);
	if (find_root(y)!=x) tree[x].pre=y;
}
void cut(int x,int y)
{
	make_root(x);
	if (find_root(y)==x&&tree[y].pre==x&&!tree[y].ls)
	{
		tree[y].pre=tree[x].rs=0;
		pushup(x);
	}
}
int main()
{
//	freopen("testdata.out","w",stdout);
	n=read(),m=read();
	for (int i=1;i<=n;i++)
		tree[i]=(node){0,0,0,0,0,0},tree[i].val=read();
	for (int i=1;i<=m;i++)
	{
		int opt=read(),x=read(),y=read();
		if (!opt)
		{
			split(x,y);
			printf("%d\n",tree[y].sum);
		}
		else if (opt==1)
		{
			link(x,y);
		}
		else if (opt==2)
		{
			cut(x,y);
		}
		else if (opt==3)
		{
			splay(x);
			tree[x].val=y;
		}
	}

	return 0;
}

评测结果