Descroption

原题链接 给你一个\(n\)个点的图，有重边有自环保证连通，最开始有\(m\)条固定的边，要求你支持加边删边改边(均不涉及最初的\(m\)条边)，每一次操作都求出图中经过\(1\)号点的环的抑或值的最大值，每个节点或边都可以经过多次(一条路经过多次则会被计算多次)。

Solution

\(~~~~\)好久都没发过博客了一定是我改题如蜗牛哎。对于每一次操作都要输出答案，考虑用线段树分治离线。先在图中随便弄出一颗以\(1\)为根的生成树，若之后再加了一条边\((u, ~v)~\)(这时一定成环便可以统计答案了)，则在线性基插入一个\(~dis[v] ~xor ~dis[u] ~xor~ w_{u, v}\)，对于三种操作，维护每条边作为该权值的起止时间，最后在线段树中统计答案就行了。这道题让我知道了我以前打的一直是假的线性基qwq %%%Rudy!!!

Code

#include <bits/stdc++.h>

#define For(i, j, k) for (register int i = j; i <= k; ++i)

#define Forr(i, j, k) for (register int i = j; i >= k; --i)

#define Travel(i, u) for (register int i = beg[u], v = to[i]; i; v = to[i = nex[i]])

using namespace std;

inline int read() {

	int x = 0, p = 1; char c = getchar();

	for (; !isdigit(c); c = getchar()) if (c == '-') p = -1;

	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

	return x * p;

}

inline void File() {

	freopen("luogu3733.in", "r", stdin);

	freopen("luogu3733.out", "w", stdout);

}

const int N = 1e3 + 5; typedef bitset<N> BI;

int e = 1, beg[N], nex[N], to[N], n, m, q, fa[N];

BI w[N], dis[N];

inline BI get() {

	static char s[N]; BI res; res.reset();

	scanf("%s", s); int len = strlen(s);

	For(i, 0, len - 1) res[i] = s[len - 1 - i] - '0';

	return res;

}

inline void write(BI t) {

	static int p;

	Forr(i, N - 5, 0) if (t[i]) { p = i; break; }

	Forr(i, p, 0) putchar(t[i] + '0'); puts("");

}

struct Linear_Bases {

	BI p[N];

	inline void insert(BI t) {

		Forr(i, N - 5, 0) if (t[i]) {

			if (!p[i].any()) { p[i] = t; return; }

			t ^= p[i];

		}

	}

	inline BI maxv() {

		BI res; res.reset();

		Forr(i, N - 5, 0) if (!res[i]) res ^= p[i];

		return res;

	}

} T;

struct node { int u, v, l, r; BI w;	} P[N << 1]; int cnt = 0;

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

inline void add(int x, int y, BI z) {

	to[++ e] = y, nex[e] = beg[x], w[beg[x] = e] = z;

	to[++ e] = x, nex[e] = beg[y], w[beg[y] = e] = z;

}

inline void dfs(int u, int f) {

	Travel(i, u) if (v ^ f) dis[v] = dis[u] ^ w[i], dfs(v, u);

}

#define lc (rt << 1)

#define rc (rt << 1 | 1)

#define mid (l + r >> 1)

vector<int> ve[N << 2];

inline void update(int rt, int l, int r, int L, int R, int v) {

	if (L <= l && r <= R) return (void) (ve[rt].push_back(v));

	if (L <= mid) update(lc, l, mid, L, R, v);

	if (R > mid) update(rc, mid + 1, r, L, R, v);

}

inline void query(int rt, int l, int r, Linear_Bases T) {

	for (int v : ve[rt]) T.insert(dis[P[v].u] ^ dis[P[v].v] ^ P[v].w);

	if (l == r) return (void) (write(T.maxv()));

	query(lc, l, mid, T), query(rc, mid + 1, r, T);

}		

int lst[N];

int main() {

	File();

	n = read(), m = read(), q = read();

	For(i, 1, n) fa[i] = i;

	For(i, 1, m) {

		int fx, fy, u = read(), v = read(); BI z = get();

		fx = find(u), fy = find(v);

		if (fx ^ fy) add(u, v, z), fa[fy] = fx;

		else P[++ cnt] = (node) {u, v, 0, q, z};

	}

	dfs(1, 0);

	static char s[8]; // <--- SKT_T1_Faker's Dream Way!

	for (register int i = 1, u, v, tt = 0; i <= q; ++ i) {

		scanf("%s", s);			

		if (s[1] == 'd') {

			u = read(), v = read(); BI z = get();

			P[lst[++ tt] = ++ cnt] = (node) {u, v, i, q, z};	

		} else if (s[1] == 'h') {

			v = lst[u = read()]; BI z = get(); P[v].r = i - 1;

			P[lst[u] = ++ cnt] = (node) {P[v].u, P[v].v, i, q, z};

		} else v = lst[u = read()], P[v].r = i - 1, lst[u] = -1;

	}	

	For(i, 1, cnt) update(1, 0, q, P[i].l, P[i].r, i);

	query(1, 0, q, T);

	return 0;

}