P3733 [HAOI2017]八纵八横 题解
zhiyangfan · · 题解
P3733 [HAOI2017]八纵八横
给出一张
n 个点m 条边的连通无向图，边带边权w_i 。有以下三种操作，共q 次：
- 在点
x,y 之间加入一条边权为w_i 的边，如果这是第i 个此种操作，则记这条新边为第i 条。- 将第
k 条新边权值改为w'_i 。- 删掉第
k 条新边，保证这条边之后不会再出现。对于初始状态和每次操作后，从图中找到一条从
1 出发，并回到1 的一条权值最大路径，路径权值定义为经过边边权的异或和。点边均可多次经过，边经过多次边权也会被计算多次。(1\le n,m\le 500,1\le q,\log_2 w_i\le 10^3 ，加边操作不超过550 次)
注意到本题走的路径有个非常重要的性质，那就是我们可以任意获得一个环。考虑从
所以现在我们的问题分为了三个部分：
- 找到所有的环。
- 计算所有环的异或最大值。
- 对某个环的权值单点修改或删除某个环。
首先对于找到所有的环，可以证明我们只需要找到一开始的连通无向图的某一生成树，则我们只需要记录剩下的边和询问加边在生成树上形成的环，就能组成所有的环。感性证明：
- 对于仅由一条非树边构成的环，已经被记录了。
- 对于由多条非树边构成的环，将这些树边在生成树上的构成的环异或组合起来就能得到。
这个过程可以用一个带权并查集实现。
然后我们需要对于找到的所有环计算异或最大值，这个显然是线性基擅长的工作。每找到一个环就把它的权值加入线性基中，询问时从高位到低位贪心即可。
最后，也是本题的难点，是对环的权值单点修改或删除某个环。注意到这两种操作其实可以并成一种，对环的权值单点异或某个值，删除就把它的权值异或到
为什么要这样选择基底呢？结论是，在这个基底上修改 不会破坏原线性基的性质和影响其他基底。首先，如我们选择的是
这样一通操作下来，我们就能在 std::bitset，时间复杂度
#include <cstdio>
#include <bitset>
#include <cstring>
const int N = 2e3 + 10; typedef std::bitset<N> bs; bs val[N];
inline void print(const bs& x)
{
int flag = 0; if (x.none()) return putchar('0'), void();
for (int i = N - 1; ~i; --i)
if (flag && x[i] == 0) putchar('0');
else if (x[i] == 1) putchar('1'), flag = 1;
}
inline void input(bs& x)
{
static char s[N]; x.reset();
scanf("%s", s); int l = strlen(s);
for (int i = 0; i < l; ++i) if (s[i] == '1') x.set(l - i - 1);
}
bs cir[N]; int toc[N], top, n, m, p;
struct Linear_basis
{
// pos_i 表示第 i 位基底对应的值的下标是多少；c_i 表示第 i 个值对应的基底；vis_i 表示 c_i 是由哪些值异或而成的。
bs c[N], vis[N]; int pos[N];
inline void modify(int x, const bs& w)
{
int p = 0;
for (int i = 1; i <= top; ++i) if (c[i].none() && vis[i][x]) { p = i; break; }
if (!p)
for (int i = 0; i < N; ++i)
if (pos[i] && vis[pos[i]][x]) { p = pos[i]; pos[i] = 0; break; }
for (int i = 1; i <= top; ++i) if (i != p && vis[i][x]) c[i] ^= c[p], vis[i] ^= vis[p];
c[p] ^= w;
for (int i = N - 1; ~i; --i)
{
if (!c[p][i]) continue;
if (!pos[i]) { pos[i] = p; break; }
c[p] ^= c[pos[i]]; vis[p] ^= vis[pos[i]];
}
}
inline bs query()
{
bs ret;
for (int i = N - 1; ~i; --i)
if (!ret[i] && pos[i]) ret ^= c[pos[i]];
return ret;
}
}lb;
struct DSU
{
int f[N], size[N]; bs dis[N];
void init(int n) { for (int i = 1; i <= n; ++i) f[i] = i, size[i] = 1; }
int getf(int x) { return x == f[x] ? x : getf(f[x]); }
bs getdis(int x) { return x == f[x] ? dis[x] : dis[x] ^ getdis(f[x]); }
void merge(int x, int y, bs w, int id)
{
int t1, t2;
if ((t1 = getf(x)) == (t2 = getf(y)))
{
bs d = getdis(x) ^ getdis(y) ^ w;
cir[++top] = d; if (id) toc[id] = top;
lb.modify(top, d);
}
if (size[t1] > size[t2]) std::swap(t1, t2);
dis[t1] = getdis(x) ^ getdis(y) ^ w;
size[t2] += size[t1]; f[t1] = t2;
}
}dsu;
int main()
{
scanf("%d%d%d", &n, &m, &p); bs w, t; char op[5]; int id = 0; dsu.init(n);
for (int i = 1; i < N; ++i) lb.vis[i][i] = 1;
for (int i = 1, x, y; i <= m; ++i)
scanf("%d%d", &x, &y), input(w), dsu.merge(x, y, w, 0);
print(lb.query()); puts("");
for (int i = 1; i <= p; ++i)
{
scanf("%s", op);
if (op[0] == 'A')
{
int x, y; scanf("%d%d", &x, &y); input(w);
dsu.merge(x, y, w, ++id); val[id] = w;
}
else
{
int k; scanf("%d", &k);
if (op[1] == 'h')
input(w), t = w, w ^= val[k], val[k] = t, lb.modify(toc[k], w), cir[toc[k]] ^= w;
else lb.modify(toc[k], cir[toc[k]]);
}
print(lb.query()); puts("");
}
return 0;
}但是，这种黑科技如果不会，在考场上想出来显然是不太现实的，所以我们考虑一个复杂度更劣，但能通过本题的离线做法。注意到，线性基这种数据结构很容易支持加入和撤销（注意区分撤销和删除）但很难支持删除，但如果题目还要求删除，我们可以考虑上线段树分治。具体来讲，我们把所有询问离线下来，处理出所有边对应的生效区间，并把这些区间挂到线段树上，对整个线段树遍历一遍，每次遍历到一个结点时加入这个结点上挂的边（类似在线做法，用带权并查集处理加环的问题），到叶子结点时，当前的线性基即为该叶子对应时间下的线性基，可以直接输出答案。离开结点时，把在这个结点做的一切事情都撤销（可以通过栈记录都干了点啥）即可。
一些特殊的问题：
- 对于一开始就加入的环，生效区间为
[0,q] 。 - 对于修改操作，可以看成删掉原来的边并加入一条新边。
总时间复杂度比在线做法多一只
#include <cstdio>
#include <bitset>
#include <vector>
#include <cstring>
const int N = 2e3 + 10; typedef std::bitset<N> bs; char op[5]; int sta[N], top;
struct edge{ int u, v; bs w; edge(int u = 0, int v = 0, bs w = 0) : u(u), v(v), w(w) { } }E[N];
inline void print(const bs& x)
{
int flag = 0; if (x.none()) return putchar('0'), void();
for (int i = N - 1; ~i; --i)
if (flag && x[i] == 0) putchar('0');
else if (x[i] == 1) putchar('1'), flag = 1;
}
inline void input(bs& x)
{
static char s[N]; x.reset();
scanf("%s", s); int l = strlen(s);
for (int i = 0; i < l; ++i) if (s[i] == '1') x.set(l - i - 1);
}
struct Linear_basis
{
bs c[N]; int st[N], tp;
inline void insert(bs x)
{
for (int i = N - 1; ~i; --i)
{
if (!x[i]) continue;
if (c[i].none()) { st[++tp] = i, c[i] = x; break; }
x ^= c[i];
}
}
inline bs query()
{
bs ret;
for (int i = N - 1; ~i; --i)
if (!ret[i] && c[i].any()) ret ^= c[i];
return ret;
}
inline void del(int pos) { while (tp != pos) c[st[tp--]].reset(); }
}lb;
struct DSU
{
int f[N], size[N]; bs dis[N];
struct mem{ int x, y, s; mem(int x = 0, int y = 0, int s = 0) : x(x), y(y), s(s) { } }st[N]; int tp;
inline void init(int n) { for (int i = 1; i <= n; ++i) f[i] = i, size[i] = 1; }
int getf(int x) { return x == f[x] ? x : getf(f[x]); }
bs getdis(int x) { return x == f[x] ? dis[x] : dis[x] ^ getdis(f[x]); }
inline void merge(edge x)
{
int u = x.u, v = x.v, t1, t2; bs w = x.w;
if ((t1 = getf(u)) == (t2 = getf(v))) return lb.insert(getdis(u) ^ getdis(v) ^ w);
if (size[t1] > size[t2]) std::swap(t1, t2), std::swap(u, v);
st[++tp] = mem(t1, t2, size[t2]); size[t2] += size[t1];
dis[t1] = getdis(u) ^ getdis(v) ^ w; f[t1] = t2;
}
inline void del(int pos) { while (tp != pos) f[st[tp].x] = st[tp].x, size[st[tp].y] = st[tp].s, dis[st[tp--].x] = 0; }
}dsu;
struct SegTree
{
#define ls(k) (k << 1)
#define rs(k) (k << 1 | 1)
struct node{ std::vector<edge> e; int l, r; }h[N << 2];
void build(int k, int l, int r)
{
h[k].l = l; h[k].r = r;
if (l == r) return ;
int mid = (l + r) >> 1; build(ls(k), l, mid); build(rs(k), mid + 1, r);
}
void change(int k, int x, int y, edge v)
{
if (x <= h[k].l && h[k].r <= y) return h[k].e.emplace_back(v), void();
int mid = (h[k].l + h[k].r) >> 1;
if (x <= mid) change(ls(k), x, y, v);
if (mid < y) change(rs(k), x, y, v);
}
void query(int k)
{
int mem1 = lb.tp, mem2 = dsu.tp;
for (auto v : h[k].e) dsu.merge(v);
if (h[k].l == h[k].r) print(lb.query()), puts("");
else query(ls(k)), query(rs(k));
lb.del(mem1); dsu.del(mem2);
}
}sgt;
int main()
{
int n, m, p; scanf("%d%d%d", &n, &m, &p); bs w; sgt.build(1, 0, p); dsu.init(n);
for (int i = 1, x, y; i <= m; ++i)
scanf("%d%d", &x, &y), input(w), sgt.change(1, 0, p, edge(x, y, w));
for (int i = 1; i <= p; ++i)
{
scanf("%s", op);
if (op[0] == 'A')
{
int x, y; scanf("%d%d", &x, &y); input(w);
E[++top] = edge(x, y, w); sta[top] = i;
}
else
{
int k;
if (op[1] == 'a')
scanf("%d", &k), sgt.change(1, sta[k], i - 1, E[k]), sta[k] = 0;
else
scanf("%d", &k), input(w), sgt.change(1, sta[k], i - 1, E[k]), sta[k] = i, E[k].w = w;
}
}
for (int i = 1; i <= top; ++i) if (sta[i]) sgt.change(1, sta[i], p, E[i]);
sgt.query(1); return 0;
}