【luogu3733】【HAOI2017】 八纵八横 (线段树分治+线性基)

Descroption

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

Solution

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

Code

#include <bits/stdc++.h>
#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<N> 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<int> 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;
}
上一篇:zhengrui集训笔记2


下一篇:sping_依赖注入的三种方式