loj#2312. 「HAOI2017」八纵八横(线性基 线段树分治)

题意

sol

线性基+线段树分治板子题。。

调起来有点自闭。。

#include<bits/stdc++.h> 
#define fi first
#define se second
#define pb push_back 
#define bit bitset<b + 1> 
using namespace std;
const int maxn = 501,  b = 1001, ss = 4001;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, q, las[ss];
struct graph {
    struct edge {
        int u, v;
        bit w;
        int nxt;
    }e[3021];
    int head[maxn], num, vis[maxn];
    graph() {
        memset(head, -1, sizeof(head));
        memset(vis, 0, sizeof(vis));
        num = 0;
    }
    bit p[b + 1], dis[maxn];
    void insert(bit s) {
        for(int i = b; ~i; i--) {
            if(s[i]) {
                if(!p[i].count()) {p[i] = s; break;}
                s = s ^ p[i];
            }
        }
    }
    void dfs(int x, int fa) {
        vis[x] = 1;
        for(int i = head[x]; ~i; i = e[i].nxt) {
            int to = e[i].v; bit w = e[i].w;
            if((i ^ 1) == fa) continue;
            if(vis[to]) insert(dis[x] ^ dis[to] ^  w);
            else {
                dis[to] = dis[x] ^ w; 
                dfs(to, i);
            }
        }
    }
    void query() {
        bit ans; ans.reset();
        for(int i = b; ~i; i--) if(ans[i] ^ (p[i][i])) ans ^= p[i];
        for(int i = b; ~i; i--) 
            if(ans[i]) {
                for(int j = i; ~j; j--) cout << ans[j];
                puts("");
                return ;
            }   
        puts("0");
    }
    void addedge(int x, int y, bit w) {
        e[num] = {x, y, w, head[x]};
        head[x] =num++;
    }
    void insert(int x, int y, bit w) {
        insert(dis[x] ^ dis[y] ^ w);
    }

}bg;
struct edge {
    int u, v;
    bit w;
}e[ss];
vector<edge> tag[ss];

#define ls k << 1
#define rs k << 1 | 1
void add(int k, int l, int r, int ql, int qr, edge v) {
    if(ql > qr) return ;
    if(ql <= l && r <= qr) {tag[k].pb(v); return ;}
    int mid = l + r >> 1;
    if(ql <= mid) add(ls, l, mid, ql, qr, v);
    if(qr  > mid) add(rs, mid + 1, r, ql, qr, v);
}
void down(int k, int l, int r, graph now) {
    if(l > r) return ;
    graph nxt = now;
    for(auto flag: tag[k]) 
        nxt.insert(flag.u, flag.v, flag.w);
    if(l == r) {
        nxt.query(); 
        return ;
    }
    int mid = l + r >> 1;
    down(ls, l, mid, nxt);
    down(rs, mid + 1, r, nxt);
}
signed main() {
    n = read(); m = read(); q = read();
    for(int i = 1; i <= m; i++) {
        int x = read(), y = read(); bit w; cin >> w;
        bg.addedge(x, y, w);
        bg.addedge(y, x, w);
    }
    memset(las, -1, sizeof(las));
    int youducuotile = 0;
    for(int i = 1; i <= q; i++) {
        char opt[10]; scanf("%s", opt + 1);
        if(opt[1] == 'a') {
            e[++youducuotile ].u = read(), e[youducuotile ].v = read();
            cin >> e[youducuotile ].w; las[youducuotile ] = i;
        } else if(opt[1] == 'c' && opt[2] == 'a') {
            int k = read(); 
            add(1, 1, q, las[k], i - 1, e[k]); 
            las[k] = -1;
        } else {
            int k = read();
            add(1, 1, q, las[k], i - 1, e[k]);
            cin >> e[k].w;
            las[k] = i;
        }
    }
    for(int i = 1; i <= q; i++)
        if(~las[i])
            add(1, 1, q, las[i], q, e[i]);
    bg.dfs(1, -1);
    bg.query();
    if(q) 
        down(1, 1, q, bg);
    return 0;
}