Descroption

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

Solution

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

Code

#include 
    
     #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
     
       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
      
        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;}