loj #2312. 「HAOI2017」八纵八横

题意：

给你一个无向连通图，可以加入边，删除或修改新加的边，每个操作后求从$1$出发回到$1$的路径的边权异或最大值。

题解：

没看到开始是连通的想了半天不会做
这题实际上就是求所有环的异或和的最大值，如果没有修改操作，这个用线性基搞就可以了。修改的话就像这题一样就好了，记下每条边带来的环的异或和是多少就好了。

代码：

#include <bits/stdc++.h>
using namespace std;

const int sz = 1000;
typedef bitset<sz> type;
int n, m, Q, num = 1, fst[510], cnt = 0, now[1010], tim = 0, nowx[1010], nowy[1010];
bool nowext[1010];
type nowc[1010];
struct edge
{
    int x, y, n;
    type c;
} e[1010];
struct basis
{
    type b[sz];
    int R[sz];
    void ins(type x, int l, int r)
    {
        for (int i = sz - 1; i >= 0; i--)
        {
            if (!x[i]) continue;
            if (b[i][i])
            {
                if (R[i] <= l) { b[i] = x; R[i] = r; return; }
                if (R[i] < r)
                {
                    swap(x, b[i]);
                    swap(R[i], r);
                }
                x ^= b[i];
            }
            else
            {
                R[i] = r;
                b[i] = x;
                return;
            }
        }
    }
    type get(int t)
    {
        type ans;
        for (int i = sz - 1; i >= 0; i--)
            if (!ans[i] && t < R[i])
                ans ^= b[i];
        return ans;
    }
} b;
struct th
{
    type c;
    int l, r;
};
vector<th> a;
type dis[510], c;
bool v[510];
char s[10];

void ins(int x, int y, bitset<sz> c)
{
    e[++num] = {x, y, fst[x], c};
    fst[x] = num;
}
void dfs(int x, int fr)
{
    v[x] = 1;
    dis[x] = dis[e[fr].x] ^ e[fr].c;
    for (int i = fst[x]; i; i = e[i].n)
    {
        if ((i ^ 1) == fr) continue;
        int y = e[i].y;
        if (v[y])
        {
            b.ins(dis[x] ^ dis[y] ^ e[i].c, 0, Q + 1);
        }
        else
        {
            dfs(y, i);
        }
    }
}
int cmp(th x, th y) { return x.l < y.l; }
void print(const type &x)
{
    bool tf = 0;
    for (int i = sz - 1; i >= 0; i--)
        if (x[i] || tf) cout << x[i], tf = 1;
    if (!tf) cout << 0;
    cout << endl;
}
int main()
{
    // freopen("c8.in", "r", stdin);
    // freopen("out", "w", stdout);
    ios::sync_with_stdio(false);
    cin >> n >> m >> Q;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y >> c;
        ins(x, y, c);
        ins(y, x, c);
    }
    dfs(1, 0);/*
    for (int i = 1; i <= n; i++)
        print(dis[i]);
    cout << endl;*/
    print(b.get(0));
    while (Q--)
    {
        cin >> s;
        tim++;
        if (s[1] == 'd')
        {
            cnt++;
            now[cnt] = tim;
            cin >> nowx[cnt] >> nowy[cnt] >> c;
            nowc[cnt] = c ^ dis[nowx[cnt]] ^ dis[nowy[cnt]];
            nowext[cnt] = 1;
        }
        else if (s[1] == 'h')
        {
            int k;
            cin >> k >> c;
            a.push_back((th){nowc[k], now[k], tim});
            now[k] = tim;
            nowc[k] = c ^ dis[nowx[k]] ^ dis[nowy[k]];
        }
        else
        {
            int k;
            cin >> k;
            a.push_back((th){nowc[k], now[k], tim});
            nowext[k] = 0;
        }
    }
    for (int i = 1; i <= cnt; i++)
        if (nowext[i])
            a.push_back((th){nowc[i], now[i], tim + 1});
    sort(a.begin(), a.end(), cmp);
    for (int i = 0; i < a.size(); i++)
    {
        // cerr << a[i].l << ' ' << a[i].r << ' ' << a[i].c << endl;
        b.ins(a[i].c, a[i].l, a[i].r);
        if (i < a.size() - 1 && a[i + 1].l != a[i].l)
        {
            for (int j = a[i].l; j < a[i + 1].l; j++)
                print(b.get(j));
        }
    }
    if (!a.empty())
        for (int i = a.back().l; i <= tim; i++)
            print(b.get(i));
}