数据是 $3\times 10^5$ 的，过不了

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
int n, m, v[MAXN];
void qread(int &a) {
	a = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') a = a * 10 - '0' + ch, ch = getchar();
}
struct LCT {
	int ch[MAXN][2], fa[MAXN], val[MAXN], rev[MAXN];
	void pushup(int x) { val[x] = val[ch[x][0]] ^ val[ch[x][1]] ^ v[x]; }
	void pushdown(int x) {
		if (rev[x]) {
			rev[x] ^= 1, rev[ch[x][0]] ^= 1, rev[ch[x][1]] ^= 1;
			swap(ch[x][0], ch[x][1]);
		}
	}
	bool isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
	void rotate(int x) {
		int y = fa[x], z = fa[y], r = ch[y][0] == x;
		if (!isroot(y)) ch[z][ch[z][0] != y] = x;
		fa[x] = z, fa[y] = x, fa[ch[x][r]] = y;
		ch[y][r ^ 1] = ch[x][r], ch[x][r] = y;
		pushup(y), pushup(x);
	}
	void splay(int x) {
		stack<int> stk;
		stk.push(x);
		int p = x, y, z;
		while (!isroot(p)) stk.push(fa[p]), p = fa[p];
		while (!stk.empty()) pushdown(stk.top()), stk.pop();
		while (!isroot(x)) {
			y = fa[x], z = fa[y];
			if (!isroot(y)) {
				if (ch[y][0] == x ^ ch[z][0] == y) rotate(x);
				else rotate(y);
			}
			rotate(x);
		}
	}
	void access(int x) {
		int t = 0;
		while (x) {
			splay(x), ch[x][1] = t, pushup(x);
			t = x, x = fa[x];
		}
	}
	void makert(int x) { access(x), splay(x), rev[x] ^= 1; }
	int find(int x) {
		access(x), splay(x);
		while (ch[x][0]) x = ch[x][0];
		return x;
	}
	void split(int x, int y) { makert(x), access(y), splay(y); }
	void link(int x, int y) { makert(x), fa[x] = y; }
	void cut(int x, int y) {
		split(x, y);
		if (ch[y][0] == x && !ch[x][1]) ch[y][0] = 0, fa[x] = 0;
	}
} t;
int main() {
	qread(n), qread(m);
	for (int i = 1; i <= n; i++) qread(v[i]), t.val[i] = v[i];
	int op, x, y, xx, yy;
	while (m--) {
		qread(op), qread(x), qread(y);
		if (op == 0) {
			t.split(x, y);
			printf("%d\n", t.val[y]);
		} else if (op == 1) {
			xx = t.find(x), yy = t.find(y);
			if (xx != yy) t.link(x, y);
		} else if (op == 2) {
			xx = t.find(x), yy = t.find(y);
			if (xx == yy) t.cut(x, y);
		} else {
			t.access(x), t.splay(x);
			v[x] = y, t.pushup(x);
		}
	}
}