tle on #5，救救孩子

做法和题解是一样的

救救孩子吧，求求了 /kel /kel

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

typedef long long ll;
const int MAXN = 1e6 + 5;

struct edge { int x, y, k; };
int N, M;
map<pair<int, int>, pair<int, int> > S;

struct linearBase {
	int T[31];
	void insert(int x) {
		for (int i = 30; i >= 0; --i) if (x & (1 << i)) {
			if (T[i]) x ^= T[i];
			else { T[i] = x; break; }
		}
	}
	int query(int x) {
		for (int i = 30; i >= 0; --i) if ((x ^ T[i]) < x) x ^= T[i];
		return x;
	}
} lb;
struct disjointSetUnion {
	int fa[MAXN], rnk[MAXN], val[MAXN];
	pair<int*, int> stk[MAXN]; int slen;
	void init() { slen = 0; for (int i = 1; i <= N; ++i) fa[i] = i, rnk[i] = 1, val[i] = 0; }
	int get(int x) { return fa[x] != x ? get(fa[x]) : x; }
	int getdis(int x) { return fa[x] != x ? (getdis(fa[x]) ^ val[x]) : 0; }
	int merge(int x, int y, int k) {
		x = get(x), y = get(y); if (rnk[x] > rnk[y]) swap(x, y); int cnt = 0;
		stk[++slen] = make_pair(&fa[x], fa[x]), stk[++slen] = make_pair(&val[x], val[x]), cnt += 2;
		fa[x] = y, val[x] = k;
		if (rnk[x] == rnk[y]) stk[++slen] = make_pair(&rnk[y], rnk[y]), ++rnk[y], ++cnt;
		return cnt;
	}
	void undo() {
		*stk[slen].first = stk[slen].second, --slen;
	}
} dsu;
struct segmentTree {
	vector<edge> V[MAXN], Q[MAXN];
	#define mid ((l + r) >> 1)
	void insModify(int o, int l, int r, int L, int R, edge p) {
		if (l == L && r == R) V[o].push_back(p);
		else {
			if (R <= mid) insModify(o << 1, l, mid, L, R, p);
			else if (L > mid) insModify(o << 1 | 1, mid + 1, r, L, R, p);
			else insModify(o << 1, l, mid, L, mid, p), insModify(o << 1 | 1, mid + 1, r, mid + 1, R, p);
		}
	}
	void insQuery(int o, int l, int r, int pos, edge p) {
		if (l == r) Q[o].push_back(p);
		else {
			if (pos <= mid) insQuery(o << 1, l, mid, pos, p);
			else insQuery(o << 1 | 1, mid + 1, r, pos, p);
		}
	}
	void Solve(int o, int l, int r) {
		int cnt = 0;
		for (edge p : V[o]) {
			if (dsu.get(p.x) == dsu.get(p.y)) lb.insert(p.k ^ dsu.getdis(p.x) ^ dsu.getdis(p.y));
			else cnt += dsu.merge(p.x, p.y, p.k ^ dsu.getdis(p.x) ^ dsu.getdis(p.y));
		}
		if (l == r) {
			for (edge p : Q[o]) {
				printf("%d\n", lb.query(dsu.getdis(p.x) ^ dsu.getdis(p.y)));
			}
		} else {
			linearBase tmp = lb;
			Solve(o << 1, l, mid);
			lb = tmp;
			Solve(o << 1 | 1, mid + 1, r);
		}
		while (cnt--) dsu.undo();
	}
} sgt;

int main() {
	scanf("%d%d", &N, &M); int op, u, v, k;
	for (int i = 1; i <= M; ++i) {
		scanf("%d%d%d", &u, &v, &k);
		S.insert(make_pair(make_pair(u, v), make_pair(k, 1)));
	}
	int Q; scanf("%d", &Q);
	for (int i = 1; i <= Q; ++i) {
		scanf("%d%d%d", &op, &u, &v);
		if (op == 1) scanf("%d", &k), S.insert(make_pair(make_pair(u, v), make_pair(k, i)));
		else if (op == 2) {
			map<pair<int, int>, pair<int, int> >::iterator it = S.find(make_pair(u, v));
			sgt.insModify(1, 1, Q, it->second.second, i - 1, edge{it->first.first, it->first.second, it->second.first});
			S.erase(it);
		} else sgt.insQuery(1, 1, Q, i, edge{u, v, 0});
	}
	for (map<pair<int, int>, pair<int, int> >::iterator it = S.begin(); it != S.end(); ++it) {
		sgt.insModify(1, 1, Q, it->second.second, Q, edge{it->first.first, it->first.second, it->second.first});
	}
	dsu.init();
	sgt.Solve(1, 1, Q);
	return 0;
}