给定 (n) 个点 (m) 条边的带权无向图，权值是小于 (2^{1000}) 的二进制数。有 (q) 次操作，每次操作可能会新增一条边，删除一条边或者修改某条边的权值。你需要在每次操作后，输出图中的最大权环，环的权值定义为环上所有边的异或和，环可以多次经过某个点或某条边。(n,m leq 500, q leq 1000)
Solution
一个很显然的 70 分暴力是直接按照 [WC2011] XOR 那题的方法做，然而线性基不支持撤销，我们要向将冗余的部分优化掉，需要另寻思路
考虑到每条边的存在时间是一个区间，容易想到线段树分治
首先搞出原图的一棵生成树，这样我们就可以让多出来的每条边对应唯一的一个环，于是每条边所对应的环的权值也就随之确定
这样问题就转化为，一开始集合中有 (m-n+1) 个数，现在我们要操作 (q) 次，每次新增一个数，删除一个数，或者修改一个数，不妨把修改一个数视为删除后再添加，那么就只有添加和删除两种操作
于是我们处理出每个数存在的时间区间，将它挂到线段树上，然后跑线段树分治
具体地，每递归到一个节点时，拷贝一份父亲节点的线性基，并在其中插入这个节点上挂的数字，就可以得到这个点的线性基
递归到叶子节点的时候，求一下线性基中的最大异或和即可
注意有些新增的边不会被删除，所以最后要把它们处理一下
#include <bits/stdc++.h>
using namespace std;
const int dbg = 0;
const int N = 1005;
const int W = 1000;
int n, m, q, ww;
struct pib {
int q;
bitset<W> w;
};
struct edge {
int u, v;
bitset<W> w;
} ed[N * 2];
vector<pib> g[N];
void print(bitset<W> b) {
for (int j = ww - 1; j >= 0; --j) cout << b[j];
}
namespace tree {
int vis[N], ontree[N / 2][N / 2], used[N / 2][N / 2];
bitset<W> dist[N / 2][N / 2];
void dfs(int p) {
vis[p] = 1;
for (pib it : g[p]) {
int q = it.q;
if (vis[q] == 0) {
ontree[p][q] = ontree[q][p] = 1;
dfs(q);
}
}
}
void calc(int p, bitset<W> *d) {
vis[p] = 1;
for (pib it : g[p]) {
int q = it.q;
if (vis[q] == 0) {
d[q] = d[p] ^ it.w;
calc(q, d);
}
}
}
void solve() {
dfs(1);
for (int i = 1; i <= n; i++) g[i].clear();
for (int i = 1; i <= m; i++) {
if (ontree[ed[i].u][ed[i].v]) {
if (used[ed[i].u][ed[i].v] == 0) {
used[ed[i].u][ed[i].v] = used[ed[i].v][ed[i].u] = 1;
g[ed[i].u].push_back({ ed[i].v, ed[i].w });
g[ed[i].v].push_back({ ed[i].u, ed[i].w });
}
}
}
for (int i = 1; i <= n; i++) {
memset(vis, 0, sizeof vis);
calc(i, dist[i]);
}
}
} // namespace tree
struct linearbase {
bitset<W> a[W + 1];
void clear() {
for (int i = 0; i <= W; i++) a[i] = 0;
}
void insert(bitset<W> k) {
for (int j = W - 1; j >= 0; --j)
if ((k >> j)[0])
if (a[j] == 0) {
a[j] = k;
break;
} else
k ^= a[j];
}
bitset<W> solve() {
bitset<W> ans;
for (int i = W - 1; i >= 0; --i)
if (a[i].count() && ans[i] == 0)
ans ^= a[i];
return ans;
}
};
char str[N];
int t1, t2, t3;
struct railway {
int t, u, v;
bitset<W> w;
} rail[N];
namespace seg {
vector<bitset<W> > a[N * 4];
int dep = 0;
bitset<W> ans[N * 4];
void modify(int p, int l, int r, int ql, int qr, bitset<W> v) {
if (l > qr || r < ql)
return;
if (l >= ql && r <= qr) {
a[p].push_back(v);
} else {
modify(p * 2, l, (l + r) / 2, ql, qr, v);
modify(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr, v);
}
}
void modify(int ql, int qr, bitset<W> v) {
if (dbg) {
cout << "seg::modify ql=" << ql << " qr=" << qr << " v=";
print(v);
cout << endl;
}
++ql;
++qr;
modify(1, 1, q + 1, ql, qr, v);
}
void solve(int p, int l, int r, linearbase b) {
++dep;
for (bitset<W> i : a[p]) b.insert(i);
if (l == r) {
ans[l] = b.solve();
} else {
solve(p * 2, l, (l + r) / 2, b);
solve(p * 2 + 1, (l + r) / 2 + 1, r, b);
}
--dep;
}
void solve() {
linearbase lb;
solve(1, 1, q + 1, lb);
}
} // namespace seg
signed main() {
ios::sync_with_stdio(false);
cin >> n >> m >> q;
for (int i = 1; i <= m; i++) {
cin >> t1 >> t2 >> str;
int len = strlen(str);
ww = max(ww, len);
for (int j = 0; j < len; j++) ed[i].w[j] = str[len - j - 1] - '0';
ed[i].u = t1;
ed[i].v = t2;
g[t1].push_back({ t2, ed[i].w });
g[t2].push_back({ t1, ed[i].w });
}
tree::solve();
using seg::modify;
using tree::dist;
using tree::ontree;
for (int i = 1; i <= m; i++) {
if (!ontree[ed[i].u][ed[i].v]) {
modify(0, q, dist[ed[i].u][ed[i].v] ^ ed[i].w);
} else {
ontree[ed[i].u][ed[i].v] = ontree[ed[i].v][ed[i].u] = 0;
}
}
int ind = 0;
for (int i = 1; i <= q; i++) {
cin >> str;
if (str[1] == 'd') {
++ind;
rail[ind].t = i;
cin >> rail[ind].u >> rail[ind].v >> str;
int len = strlen(str);
ww = max(ww, len);
for (int j = 0; j < len; j++) rail[ind].w[j] = str[len - j - 1] - '0';
} else if (str[1] == 'h') {
cin >> t1;
modify(rail[t1].t, i - 1, rail[t1].w ^ dist[rail[t1].u][rail[t1].v]);
cin >> str;
int len = strlen(str);
ww = max(ww, len);
rail[t1].w = 0; //!
for (int j = 0; j < len; j++) rail[t1].w[j] = str[len - j - 1] - '0';
rail[t1].t = i;
} else if (str[1] == 'a') {
cin >> t1;
if (dbg) {
cout << "dbg Cancel ";
print(rail[t1].w);
cout << " ";
print(dist[rail[t1].u][rail[t1].v]);
cout << endl;
}
modify(rail[t1].t, i - 1, rail[t1].w ^ dist[rail[t1].u][rail[t1].v]);
rail[t1].t = 0;
}
}
for (int i = 1; i <= ind; i++)
if (rail[i].t) {
modify(rail[i].t, q, rail[i].w ^ dist[rail[i].u][rail[i].v]);
}
seg::solve();
using seg::ans;
for (int i = 1; i <= q + 1; i++) {
print(ans[i]);
cout << endl;
}
}