如题

#include<bits/stdc++.h>

using namespace std;

const int N=100005;

int n,m; 
int val[N],ch[N][2];

// Splay 部分
int siz[N],cnt[N],fa[N],tag[N];

bool get(int u) {return u==ch[fa[u]][1];}
bool isroot(int u) {return ch[fa[u]][0]!=u && ch[fa[u]][1]!=u;}
void pushup(int u) {
	siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+1;
	cnt[u]=cnt[ch[u][1]]^cnt[ch[u][0]]^val[u];
}
void pushdown(int u) {
	if(tag[u]) {
		tag[ch[u][0]]^=1,tag[ch[u][1]]^=1,tag[u]=0;
		swap(ch[u][0],ch[u][1]);
	}
}

void update(int u) {
	if(!isroot(u)) update(fa[u]);
	pushdown(u);
}

void rorate(int u) {
	int v=fa[u];int f=fa[v],chk=get(u);
	if(!isroot(v)) ch[f][get(v)]=u;
	ch[v][chk]=ch[u][chk^1]; if(ch[u][chk^1]) fa[ch[u][chk^1]]=v;
	ch[u][chk^1]=v;
	fa[v]=u,fa[u]=f;
	pushup(v);pushup(u);pushup(f);
}

void splay(int u) {
	update(u);
	while(!isroot(u)){
		int v=fa[u],f=fa[v];
		if(!isroot(v)) (get(u)==get(v))?rorate(v):rorate(u);
		rorate(u);
	}
}

int access(int u) {
	int p;
	for(p=0;u;p=u,u=fa[u]) {
		cout << "AC" << u << endl;
		splay(u);
		ch[u][1]=p;
		pushup(u);
	}
	return p;
}

void makeroot(int u) {
	u=access(u);
	swap(ch[u][0],ch[u][1]);tag[u]^=1;
}

void link(int u,int v) {
	makeroot(u);
	splay(u);
	fa[u]=v;
}

void split(int u,int v) {makeroot(u);access(v);splay(v);}
void cut(int u,int v) {
	split(u,v);
	ch[v][get(u)]=fa[u]=0;
} 

int find(int u) {
	access(u);
	splay(u);
	pushdown(u);
	while(ch[u][0]) u=ch[u][0],pushdown(u);
	splay(u);
	return u;
}

map<pair<int,int>,bool> M;

int main() {
	cin >> n >> m;
	for(int i=1;i<=n;++i) cin >> val[i];
	for(int i=1;i<=n;++i) pushup(i);
	
	int op,u,v;
	for(int i=1;i<=m;++i) {
		cin >> op;
		if(op==0) {
			cin >> u >> v;
			split(u,v);
			//cout << fa[u] << ' ' << fa[v] << ' ' << ch[v][get(u)] << ' ' << ch[u][get(v)] << endl;
			cout << cnt[v] << endl;
		}else if(op==1) {
			cin >> u >> v;
			if(find(u)==find(v)) continue;
			link(u,v);M[make_pair(u,v)]=1;
		}else if(op==2){
			cin >> u >> v;
			if(!M[make_pair(u,v)]) continue;
			M[make_pair(u,v)]=0;
			cut(u,v);
		}else {
			cin >> u >> v;
			splay(u);
			val[u]=v;
			pushup(u);
		}
	}
	
	return 0;
}