非常经典的使用线段树分治维护最大异或和路径的题目。

首先看到最大异或和路径，就可以迅速联想起 [WC2011]最大 XOR 和路径。发现其实就是把每个时刻的线性基搞出来就行了，由于这个题是求 $1 \rightarrow 1$ 的路径所以甚至不需要找链。

每个时刻都重做一次肯定是会 $\text{T}$ 的。于是我们考虑一个经典做法，就是一开始的时候先随便找一个原图的生成树，然后将原图中已经存在的环丢进线性基。由于原图中的边是不会改变边权或者被删掉的，所以我们就可以不管了。对于后面的每一次加边，我们把这条新边和原图的生成树所构成的那个环给丢进线性基里面。容易证明这些插入线性基中的环可以表示出来新图中的所有环（感性理解）。

由于题目中说 $w$ 的二进制表示下的位数 $len \leq 1000$，所以必须使用 $\text{bitset}$ 来存储边的权值和线性基里面的数。

原图的生成树和环可以一开始直接用一遍 $\text{dfs}$ 得到（过程中可以直接用一开始处理出来的值，不需要带权并查集），中间的一次加边操作的时间复杂度是 $O(\frac{len ^ 2}{\omega})$ 的。于是只有加边操作的情况我们就可以在 $O(m + \frac{Q len^2}{\omega})$ 的复杂度内完成。

那么现在考虑一下有了改边权和删除操作的情况。由于改边权我们可以看作是撤销掉原来的这条边，加入一条新的权值是 $w'$ 的边，所以我们就只用考虑如何删除。线性基这个东西是不太好直接进行删除的，于是考虑线段树分治把删除变成撤销。这个是比较简单的，把每条边的时间区间 $[l, r]$ 求出来然后插入线段树里面，然后递归到每一个节点的时候开一个新的线性基来备份当前状态（由于线段树高是 $\log Q$ 的，所以空间复杂度是 $len \log Q$，不会 $\text{MLE}$），回溯的时候还原线性基即可。

时间复杂度 $O(m + \frac{Q \log Q len^2}{\omega})$。开了 $\text{O2}$ 之后跑的飞快。

#include<bits/stdc++.h>
#define ls (num << 1)
#define rs ((num << 1) | 1)
#define mid ((l + r) >> 1)
#define pb push_back

using namespace std;

const int N = 1e3 + 7;
const int MT = 1e3 + 7;

#define bi bitset<MT + 1>

struct Ope {
    int u, v;
    bi w;
};

int n, m, Q, k;
int head[N], pre[N], ver[N];
int st[N], ed[N], unc[N], ti[N];
int cnt = 0, vis[N];
bi val[N], Xor[N], B[MT + 1], ept, col[MT + 1];
vector<Ope> upd[N << 2];
bi Ansn[MT + 1];

void add_edge(int u, int v, bi w) {
    pre[++cnt] = head[u];
    head[u] = cnt;
    ver[cnt] = v, val[cnt] = w;
    return;
}

bool ins(bi x) {
    bool flag = 0;
    for(int i = MT; ~i; --i) {
        if(x[i]) {
            if(B[i] == ept) {
                flag = 1, B[i] = x;
                break;
            }
            else x ^= B[i];
        }
    }    
    return flag;
}

bi qmx() {
    bi Ans;
    for(int i = MT; ~i; --i) {
        if(B[i] == ept) continue;
        else if(Ans[i] == 0) Ans ^= B[i];
    }
    return Ans;
}

void dfs(int nown) {
    if(vis[nown]) return;
    vis[nown] = 1;
    for(int i = head[nown]; i; i = pre[i]) {
        int v = ver[i];
        if(vis[v]) {
            ins((Xor[nown] ^ Xor[v] ^ val[i]));
            continue;
        }
        Xor[v] = Xor[nown] ^ val[i];
        dfs(v);
    }
    return;
}

void update(int num, int l, int r, int a, int b, Ope v) {
    if(a <= l && b >= r) {
        upd[num].pb(v);
        return;
    }
    if(a <= mid) update(ls, l, mid, a, b, v);
    if(b > mid) update(rs, mid + 1, r, a, b, v);
    return;
}

void solve(int num, int l, int r) {
    bi bacB[MT + 1];
    for(int i = 0; i <= MT; ++i) bacB[i] = B[i];
    for(Ope op : upd[num]) {
        int u = op.u, v = op.v; bi w = op.w;
        ins(Xor[u] ^ Xor[v] ^ w);
    }
    if(l == r) {
        Ansn[l] = qmx();
        for(int i = 0; i <= MT; ++i) B[i] = bacB[i];
        return;
    }
    solve(ls, l, mid), solve(rs, mid + 1, r);
    for(int i = 0; i <= MT; ++i) B[i] = bacB[i];
    return;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m >> Q;
    for(int i = 1; i <= m; ++i) {
        int u, v; bi w; string s;
        cin >> u >> v;
        cin >> s; reverse(s.begin(), s.end());
        for(int j = 0; j < s.length(); ++j) if(s[j] - '0' == 1) w.set(j);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    dfs(1);
    Q++;
    for(int i = 2; i <= Q; ++i) {
        string opt; int x, y; bi z;
        cin >> opt;
        if(opt[0] == 'A') {
            ++k; cin >> x >> y; string s;
            cin >> s; reverse(s.begin(), s.end());
            for(int j = 0; j < s.length(); ++j) if(s[j] - '0' == 1) z.set(j);
            unc[k] = 1, st[k] = x, ed[k] = y, col[k] = z, ti[k] = i;
        }
        else if(opt == "Cancel") {
            cin >> x; unc[x] = 0;
            update(1, 1, Q, ti[x], i - 1, (Ope){st[x], ed[x], col[x]});
        }
        else {
            cin >> x; string s;
            cin >> s; reverse(s.begin(), s.end());
            for(int j = 0; j < s.length(); ++j) if(s[j] - '0' == 1) z.set(j);
            update(1, 1, Q, ti[x], i - 1, (Ope){st[x], ed[x], col[x]});
            ti[x] = i, col[x] = z;
        }
    }
    for(int i = 1; i <= k; ++i) {
        if(!unc[i]) continue;
        update(1, 1, Q, ti[i], Q, (Ope){st[i], ed[i], col[i]});
    }
    solve(1, 1, Q);
    for(int i = 1; i <= Q; ++i) {
        int cur = MT;
        while(Ansn[i][cur] == 0 && cur) cur--;
        for(int j = cur; ~j; --j) cout << Ansn[i][j];
        cout << '\n';
    }
    return 0;
}

/* 
    Author: _LiMLE_
    start coding at: 15:08
    finish debugging at: 15:50
*/

视频：G71 可删除线性基+离线处理 P3733 [HAOI2017] 八纵八横
视频：G72 线段树分治+线性基 P3733 [HAOI2017] 八纵八横