可删除线性基板子。
显然我们贪心的希望越高位的线性基越早被删除,于是我们对于每一位顺便记录一下被删除的时间。如果要插入的数被删除时间比较晚,则与交换该位于要插入的数。其它和普通线性基一样。
其它部分参见 [WC2011]最大XOR和路径。
#include <bits/stdc++.h>
#define bt bitset<1005>
using namespace std;
const int N = 1005;
typedef long long ll;
inline int read() {
register int s = 0, f = 1; register char ch = getchar();
while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
return s * f;
}
int stk[N];
inline void readw(bt &b) {
b = 0;
register char ch = getchar(); int m = 0;
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) stk[m++] = ch & 15, ch = getchar();
--m;
for (int i = 0; i <= m; ++i) b[i] = stk[m - i];
}
inline char readc() {
while (!isalpha(getchar()));
return getchar();
}
struct base {
bt a[1005];
int tms[1005];
inline bt& operator [] (int x) { return a[x]; }
inline base() { memset(a, 0, sizeof a); memset(tms, 0, sizeof tms); }
inline void insert(bt x, int t) {
for (int i = 1000; ~i; --i) {
if (!x[i]) continue;
if (tms[i] < t) { swap(a[i], x); swap(tms[i], t); }
if (!t) break;
x ^= a[i];
}
}
inline bt qmx(int t) {
bt res = 0;
for (int i = 1000; ~i; --i)
if (tms[i] > t && !res[i]) res ^= a[i];
return res;
}
} t;
inline void print(bt b) {
int t = -1;
for (int i = 1000; ~i; --i)
if (b[i]) { t = i; break; }
if (t == -1) puts("0");
else {
while (~t) putchar(b[t--] ^ 48);
putchar('\n');
}
}
struct edge {
int head, to, nxt;
bt val;
} ed[N << 1];
int en = 0;
inline void addedge(int from, int to) {
bt b; readw(b);
ed[++en].to = to; ed[en].val = b; ed[en].nxt = ed[from].head; ed[from].head = en;
ed[++en].to = from; ed[en].val = b; ed[en].nxt = ed[to].head; ed[to].head = en;
}
bt dis[N];
bool vis[N];
inline void dfs(int now) {
for (int i = ed[now].head; i; i = ed[i].nxt) {
int v = ed[i].to;
if (vis[v]) t.insert(dis[now] ^ dis[v] ^ ed[i].val, 1e9);
else {
vis[v] = 1;
dis[v] = dis[now] ^ ed[i].val;
dfs(v);
}
}
}
int tim = 0, n, m, q, R[N];
int op[N], X[N], Y[N], id[N], pos[N];
bt Z[N];
int k = 0;
int main() {
// freopen("c7.in", "r", stdin); freopen("c7.out", "w", stdout);
n = read(); m = read(); q = read();
for (int i = 1, u, v; i <= m; ++i) {
u = read(); v = read();
addedge(u, v);
} dfs(1);
print(t.qmx(0));
for (int i = 1; i <= q; ++i) {
char c = readc();
if (c == 'd') {
op[i] = 1;
X[i] = read(); Y[i] = read(); readw(Z[i]);
pos[id[i] = ++k] = i;
} else if (c == 'h') {
op[i] = 1; int x = read();
X[i] = X[pos[x]]; Y[i] = Y[pos[x]];
R[pos[x]] = i; pos[x] = i;
readw(Z[i]);
} else if (c == 'a') {
int x = read();
op[i] = 3;
R[pos[x]] = i;
}
}
for (int i = 1; i <= q; ++i) {
if (op[i] == 1 && !R[i]) R[i] = 1e9;
if (op[i] == 1)
t.insert(dis[X[i]] ^ dis[Y[i]] ^ Z[i], R[i]);
print(t.qmx(i));
}
return 0;
}