[题解] CF938G Shortest Path Queries

Shortest Path Queries

给你一张无向连通图，支持三种操作：

1. 插入一条边 \((u, v, w)\)。
2. 删除一条边。
3. 求 \((u, v)\) 之间的异或最短路。

\(n, m, 1 < 2^{30}\)。

先考虑异或最短路怎么求，这部分和 最大XOR和路径 是一样的。就是把图上的环都扔到一个线性基里，每次查询就是线性基上查询异或最小值。
再考虑加上加边操作。就是维护一棵图的生成树，要是加入的这一条边没有形成环就把它加到生成树中，形成了环就是把环长扔到线性基里，环长可以通过生成树上到根的路径的异或和来算。这部分用并查集维护即可。
加上删边就是套一个线段树分治，再把并查集改成可撤销并查集。
时间复杂度 \(O(n \log^2 n)\)。

constexpr int MAXN = 2e5 + 9, MAXM = MAXN << 1;
int n, m, q, st[MAXM], ed[MAXM];
map<pii, int> idx;
pair<int, int> qry[MAXN];
array<int, 3> E[MAXM];

struct Base_Line {
	static constexpr int N = 31;
	int a[N];
	
	void Insert(int x) {
		for (int i = 30; ~i; i --) if (x >> i & 1) {
			if (a[i]) x ^= a[i];
			else { a[i] = x; break; }
		}
		return;
	}
	int Query(int x) {
		for (int i = 30; i >= 0; i --)
			if (x >> i & 1) x ^= a[i];
		return x;
	}
} ds;

struct Disjoint {
	int fa[MAXN], sz[MAXN], dis[MAXN];
	vector<pair<int, int> > stk;
	
	void Init(int n) {
		for (int i = 1; i <= n; i ++)
			fa[i] = i, dis[i] = 0, sz[i] = 1;
		return;
	}
	int Find(int u) {
		return fa[u] == u ? u : Find(fa[u]);
	}
	int Get_Dis(int u) {
		return fa[u] == u ? 0 : dis[u] ^ Get_Dis(fa[u]);
	}
	bool Merge(int u, int v, int w) {
		w ^= Get_Dis(u) ^ Get_Dis(v);
		u = Find(u), v = Find(v);
		if (u == v) return false;
		if (sz[u] > sz[v]) swap(u, v);
		stk.emplace_back(u, v);
		fa[u] = v, dis[u] ^= w, sz[v] += sz[u];
		return true;
	}
	void Reset() {
		auto [u, v] = stk.back(); stk.pop_back();
		fa[u] = u, sz[v] -= sz[u], dis[u] = 0; return;
	}
} D;

namespace Segment_Tree {
	vector<int> upd[MAXN << 2];
	
	void Update(int l, int r, int id, int L = 1, int R = q, int p = 1) {
		if (l <= L && R <= r) return upd[p].emplace_back(id), void();
		int Mid = L + R >> 1;
		if (l <= Mid) Update(l, r, id, L, Mid, p << 1);
		if (Mid < r) Update(l, r, id, Mid + 1, R, p << 1 | 1);
		return;
	}
	void Solve(int L = 1, int R = q, int p = 1) {
		int tp = D.stk.size();
		Base_Line ret = ds;
		auto Get_Dis = [&](int u, int v) { return D.Get_Dis(u) ^ D.Get_Dis(v); };
		for (auto i : upd[p]) {
			auto [u, v, w] = E[i];
			if (D.Find(u) == D.Find(v)) ds.Insert(Get_Dis(u, v) ^ w);
			else D.Merge(u, v, w);
		}
		int Mid = L + R >> 1;
		if (L == R) {
			auto [u, v] = qry[L];
			if (u) Write(ds.Query(Get_Dis(u, v)), '\n');
		}
		else Solve(L, Mid, p << 1), Solve(Mid + 1, R, p << 1 | 1);
		while (D.stk.size() ^ tp) D.Reset(); ds = ret;
		return;
	}
}

void slv() {
	n = Read<int>(), m = Read<int>();
	for (int i = 1; i <= m; i ++) {
		int u = Read<int>(), v = Read<int>(), w = Read<int>();
		E[i] = {u, v, w}, idx[make_pair(u, v)] = i, st[i] = 1, ed[i] = -1;
	}
	q = Read<int>();
	for (int i = 1; i <= q; i ++) {
		int opt = Read<int>();
		if (opt == 1) {
			int u = Read<int>(), v = Read<int>(), w = Read<int>();
			E[++ m] = {u, v, w}, idx[make_pair(u, v)] = m, st[m] = i, ed[m] = -1;
		} else if (opt == 2) {
			int u = Read<int>(), v = Read<int>();
			ed[idx[make_pair(u, v)]] = i - 1;
		} else {
			int u = Read<int>(), v = Read<int>();
			qry[i] = {u, v};
		}
	}
	for (int i = 1; i <= m; i ++) {
		if (ed[i] == -1) ed[i] = q;
		if (st[i] <= ed[i])Segment_Tree::Update(st[i], ed[i], i);
	}
	D.Init(n); Segment_Tree::Solve();
	return;
}