【题解】loj#2312 [HAOI2017]八纵八横

其实不是什么难题,只是因为「写起来很麻烦」+「单独拿出来方便记忆」所以单独开一篇。

Anihc 国有 $n$ 个城市,这 $n$ 个城市从 $1$ 编号,$1$ 号城市为首都。城市间初始时有 $m$ 条高速公路,每条高速公路都有一个非负整数的经济影响因子,每条高速公路的两端都是城市(可能两端是同一个城市),保证任意两个城市都可以通过高速公路互达。

Anihc 国正在筹划「八纵八横」的高铁建设计划,计划要修建一些高速铁路,每条高速铁路两端也都是城市(可能两端是同一个城市),也都有一个非负整数的经济影响因子。国家还计划在「八纵八横」计划建成之后,将「一带一路」扩展为「一带一路一环」,增加「内陆城市经济环」即选择一条从首都出发沿若一系列高铁与高速公路走的路径,每条高铁或高速公路可以经过多次,每座城市也可以经过多次,最后路径又在首都结束。令「内陆城市经济环」的 $\rm GDP$ 为依次将这条路径上所经过的高铁或高速公路的经济影响因子异或起来(一条路经过多次则会被计算多次)。

现在 Anihc 在会议上讨论「八纵八横」的建设计划方案,他们会不断地修改计划方案,希望你能实时反馈对于当前的「八纵八横」的建设计划的方案「内陆城市经济环」的最大是多少。

初始时,八纵八横计划中不包含任何—条高铁,有以下三种操作:

Add x y z 在计划中给在城市 $x$ 和城市 $y$ 之间建设一条高铁,其经济影响因子为 $z$,如果这是第 $k$ 个 Add 操作,则将这条高铁命名为 $k$ 号高铁。

Cancel k 将计划中的 $k$ 号高铁取消掉,保证此时 $k$ 号高铁一定存在。

Change k z 表示将第 $k$ 号高铁的经济影响因子更改为 $z$,保证此时 $k$ 号高铁一定存在.

$\rm Sol$

不得不说这题有点恶心…因为他需要 bitset,于是各种操作就很不优美。

大概就是考虑用线段树分治去维护边的存在性。那么接下来就是一开始随便 $dfs$ 出一个生成树来,然后每次询问时,发现对于每个合法的方案都是从 $1$ 开始的一个环。 那么考虑最后一定是一些环套起来,所以可以直接在线性基里面查询。

做这题时发现,这么做的正确性在于,可以随便生成一棵树。同时生成出来的环也具有「生成子集」的性质,也就是说可以据此生成所有 剩下未被统计的环。要证明其实也不难。

所以可能这种「线性基+生成树+环生成子集」的结合是“完洽”的,即彼此有着共同的性质,这种搭配似乎不是很常见?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#define gcr getchar
#define p_b push_back
#define to(k) E[k].to
#define val(k) E[k].val
#define next(k) E[k].next

const int L = 1010 ;
const int N = 6010 ;
const int M = 6010 ;

int len ;
char s[L] ;
int n, m, q ;
struct Edge{
int to, next ;
bitset <L> val ;
}E[M << 1] ;
struct edge{
int u, v, l, r ;
bitset <L> val ;
}e[M] ;
bool vis[N] ;
bitset <L> f[N] ;
bitset <L> ans[N] ;
vector <edge> S[N * 3] ;
int head[N], cnt, tot, k ;

namespace xxj{
bitset<L> base[L] ;
int Insert(bitset<L> x){
for (int i = L - 1 ; ~i ; -- i)
if (x[i]){
if (base[i][i]) x ^= base[i] ;
else return base[i] = x, i ;
}
return -1 ;
}
bitset<L> Query(){
bitset<L> res ; res.reset() ;
for (int i = L - 1 ; ~i ; -- i)
if (res[i] ^ base[i][i]) res ^= base[i] ;
return res ;
}
}
using namespace xxj ;
void qr(int &x){
x = 0 ; char c = gcr() ;
while (c > '9' || c < '0') c = gcr() ;
while (isdigit(c)) x = x * 10 + c - 48, c = gcr() ;
}
void out_put(bitset <L> x){
bool flag = 0 ;
for (int i = L - 1 ; ~i ; -- i)
if (!x[i])
{if (flag) putchar('0') ;}
else putchar('1'), flag = 1 ;
puts("") ;
}
bitset<L> get_bit(){
scanf("%s", s + 1) ;
len = strlen(s + 1) ;
bitset <L> ret ; ret.reset() ;
for (int i = 1 ; i <= len ; ++ i)
if (s[i] == '1') ret.set(len - i) ;
return ret ;
}
void add(int u, int v, bitset<L> w){
to(++ cnt) = v, val(cnt) = w ;
next(cnt) = head[u], head[u] = cnt ;
to(++ cnt) = u, val(cnt) = w ;
next(cnt) = head[v], head[v] = cnt ;
}
void update(int rt, int l, int r, int ul, int ur, edge val){
if (ul <= l && r <= ur)
return S[rt].p_b(val), void() ;
int mid = (l + r) >> 1 ;
if (ul <= mid) update(rt << 1, l, mid, ul, ur, val) ;
if (ur > mid) update(rt << 1 | 1, mid + 1, r, ul, ur, val) ;
}
void solve(int rt, int l, int r){
vector <int> O ;
int mid = (l + r) >> 1 ;
for (int i = 0 ; i < S[rt].size() ; ++ i){
int u = S[rt][i].u ;
int v = S[rt][i].v ;
int d = Insert(S[rt][i].val ^ f[u] ^ f[v]) ;
if (d >= 0) O.p_b(d) ; //,cout <<d<<endl;
}
if (l == r) ans[l] = Query() ;
else solve(rt << 1, l, mid),
solve(rt << 1 | 1, mid + 1, r) ;
for (int i = 0 ; i < O.size() ; ++ i) base[O[i]].reset() ;
}
void dfs(int u){
vis[u] = 1 ; //cout << u << endl ;
for (int k = head[u] ; k ; k = next(k)){
if (vis[to(k)])
Insert(f[u] ^ f[to(k)] ^ val(k)) ;
else f[to(k)] = f[u] ^ val(k), dfs(to(k)) ;
}
}
int main(){
cin >> n >> m >> q ; int u, v ;
for (int i = 1 ; i <= m ; ++ i)
qr(u), qr(v), add(u, v, get_bit()) ;
dfs(1) ;
//for (int i = 1 ; i <= n ; ++ i) cout << f[i].count() << endl ;
for (int i = 1 ; i <= q ; ++ i){
scanf("%s", s + 1) ;// cout << i << endl ;
if (s[1] == 'A')
++ tot, qr(e[tot].u), qr(e[tot].v),
e[tot].val = get_bit(), e[tot].l = i, e[tot].r = q ;
else if (s[2] == 'a')
qr(u),
update(1, 0, q, e[u].l, i - 1, e[u]), e[u].l = -1 ;
else qr(u), update(1, 0, q, e[u].l, i - 1, e[u]),
e[u].l = i, e[u].val = get_bit(), e[u].r = q ;
}
// for (int i = 1 ; i <= tot ; ++ i)
// cout << e[i].l << " " << e[i].u << " " << e[i].v << " " << e[i].val.count() << endl ;
// cout << 2333 << endl ;
for (int i = 1 ; i <= tot ; ++ i)
if (~e[i].l) update(1, 0, q, e[i].l, q, e[i]) ;
solve(1, 0, q) ;
for (int i = 0 ; i <= q ; ++ i) out_put(ans[i]) ; return 0 ;
}