长跑[BZOJ2959]

#include <bits/stdc++.h>
#define N 150005
using namespace std;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
	return x * f; 
}

namespace LCT{
	int Fa[N], fa[N], ch[N][2], sum[N], val[N], tag[N];
	
	int find(int x) { return Fa[x] == x ? x : Fa[x] = find(Fa[x]); }
	inline bool isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
	inline void pushup(int x) { sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + val[x]; }
	inline void rev(int x) { swap(ch[x][0], ch[x][1]); tag[x] ^= 1; }
	inline void pushdown(int x) {
		if (!tag[x]) return; tag[x] = 0;
		if (ch[x][0]) rev(ch[x][0]); if (ch[x][1]) rev(ch[x][1]);
 	}
	inline void rotate(int x) {
		int y = fa[x], z = fa[y], k = (ch[y][1]==x);
		if (!isroot(y)) ch[z][ch[z][1]==y] = x;
		fa[x] = z;
		ch[y][k] = ch[x][!k]; fa[ch[x][!k]] = y;
		ch[x][!k] = y; fa[y] = x;
		pushup(y); pushup(x);
	}
	int stk[N], top;
	inline void splay(int x) {
		stk[top=1] = x;
		for (int i = x; !isroot(i); i = fa[i]) stk[++top] = fa[i];
		while (top) pushdown(stk[top--]);
		while (!isroot(x)) {
			int y = fa[x], z = fa[y];
			if (!isroot(y)) ((ch[y][1]==x)^(ch[z][1]==y)) ? rotate(x) : rotate(y);
			rotate(x);
		}
	}
	inline void access(int x) {
		for (int i = 0; x; i = x, x = find(fa[x])) {
			splay(x); ch[x][1] = i; 
			if (i) fa[i] = x; 
			pushup(x);
		}
	}
	inline void makeroot(int x) {
		access(x); splay(x); rev(x);
	}
	inline void split(int x, int y) {
		makeroot(x); access(y); splay(y);
	}
	inline void link(int x, int y) {
		makeroot(x); fa[x] = y;
	}
	queue<int> q;
	inline void merge(int x, int y) {
		split(x, y);
		q.push(y);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			Fa[find(u)] = y;
			if (ch[u][0]) q.push(ch[u][0]);
			if (ch[u][1]) q.push(ch[u][1]);
			ch[u][0] = ch[u][1] = 0;  
		}
		val[y] = sum[y]; 
	}
}

int n, m, Fa[N], a[N];

int find(int x) { return Fa[x] == x ? x : Fa[x] = find(Fa[x]); }
void Link(int x, int y) {
	int fx = LCT::find(x), fy = LCT::find(y);
	if (fx == fy) return;
	int u = find(x), v = find(y);
	if (u != v) {
		Fa[u] = v;
		LCT::link(fx, fy);
	} else {
		LCT::merge(fx, fy);
	}  
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i++) a[i] = LCT::val[i] = read();
	for (int i = 1; i <= n; i++) Fa[i] = LCT::Fa[i] = i;
	for (int i = 1, tp, x, y; i <= m; i++) {
		tp = read(); x = read(); y = read();
		if (tp == 1) {
			Link(x, y);
		} else if (tp == 2) {
			int v = y - a[x];
			a[x] = y;
			int fx = LCT::find(x);
			LCT::makeroot(fx);
			LCT::val[fx] += v;
			LCT::pushup(fx);
		} else {
			if (find(x) != find(y)) puts("-1");
			else {
				int fx = LCT::find(x), fy = LCT::find(y);
				LCT::split(fx, fy);
				printf("%d\n", LCT::sum[fy]);
			} 
		}
	}
	return 0;
}