rt QAQ

#include<bits/stdc++.h>
#define lt(cur) tree[cur].lt
#define rt(cur) tree[cur].rt
#define fa(cur) tree[cur].fa
#define to(cur) tree[cur].to 
#define int long long
using namespace std;
const int cxk=1e5+5;
struct ikun
{
	int val,pt,lt,rt,fa,to,sum;
	bool tag;
}tree[cxk];
vector<bool>v;
int n,m;
void pushup(int cur)
{
	tree[cur].sum=(tree[lt(cur)].sum^tree[rt(cur)].sum^tree[cur].val);
	if(lt(cur))
		fa(lt(cur))=cur;
	if(rt(cur))
		fa(rt(cur))=cur;
}
void pushdown(int cur)
{
	if(tree[cur].tag==0)
		return;
	swap(lt(cur),rt(cur));
	tree[lt(cur)].tag^=1;
	tree[rt(cur)].tag^=1;
	tree[cur].tag=0;
}
void split(int cur,int&x,int&y)
{
	if(v.size()==0)//我就是根！ 
	{
		pushdown(cur);
		x=cur;
		y=rt(cur);
		rt(cur)=0;
	}
	else if(v.back()^tree[cur].tag)//右儿子 
	{
		v.pop_back();
		pushdown(cur);
		x=cur;
		split(rt(cur),rt(x),y);
	}
	else
	{
		v.pop_back();
		pushdown(cur);
		y=cur;
		split(lt(cur),x,lt(y));
	}
	pushup(cur);
}
void merge(int&cur,int x,int y)
{
	if(x==0||y==0)
	{
		cur=x+y;
		return;
	}
	if(tree[x].pt<tree[y].pt)
	{
		pushdown(x);
		cur=x;
		merge(rt(cur),rt(x),y);
	}
	else
	{
		pushdown(y);
		cur=y;
		merge(lt(cur),x,lt(y));
	}
	pushup(cur);
}
bool notroot(int cur)
{
	if(cur==0)
		return 0;
	return lt(fa(cur))==cur||rt(fa(cur))==cur;
}
int ffind(int cur)
{
	v.clear();
	for(;notroot(cur);cur=fa(cur))
		v.push_back(rt(fa(cur))==cur);
	return cur;
}
int front(int cur)
{
	cur=ffind(cur);
	//cout<<cur<<" ";
	pushdown(cur);
	for(;lt(cur);pushdown(cur))
		cur=lt(cur);
	return cur;
}
int access(int cur)
{
	int root=0;
	for(;cur;cur=to(front(root)))
	{
		int r1=0,r2=0;
		split(ffind(cur),r1,r2);
		to(front(root))=0;
		merge(root,r1,root);
		to(front(r2))=cur;
	}
	return root;
}
int find(int cur)
{
	return front(access(cur));
}
void makeroot(int cur)
{
	tree[access(cur)].tag^=1;
}
void link(int x,int y)
{
	if(find(x)==find(y))//在同一棵树里面，再连就有环了
		return;
	makeroot(x);//x成为根
	to(x)=y;
	return;
}
void cut(int x,int y)
{
	if(find(x)!=find(y))
		return;
	makeroot(x);
	access(y);
	access(x);
	if(front(y)==y)
		to(y)=0;
}
int query(int x,int y)
{
	makeroot(x);
	access(y);
	int r1=0,r2=0,ans=0;
	split(ffind(y),r1,r2);
	ans=tree[r1].sum;
	merge(r1,r1,r2);
	return ans;
	//return tree[access(y)].sum;
}
void update(int x,int val)
{
	int r1=0,r2=0;
	split(ffind(x),r1,r2);
	tree[x].val=val;
	merge(r1,r1,r2);
}
signed main()
{
//	freopen("114.txt","r",stdin);
//	freopen("114.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	srand(time(0));
	cin>>n>>m;
	for(int i=1,x;i<=n;i++)
	{
		cin>>x;
		tree[i]={x,rand(),0,0,0,0,x,0};
	}
	for(int opt,x,y;m--;)
	{
		cin>>opt>>x>>y;
		if(opt==0)
			cout<<query(x,y)<<"\n";
		if(opt==1)
			link(x,y);
		if(opt==2)
			cut(x,y);
		if(opt==3)
			update(x,y);
	}
}

我是用fhq-treap维护的，各位splay党没意见吧^v^