[Codeforces938G] Shortest Path Queries

题解

把操作离线,然后分治,把问题变成只需要支持加边,回滚,维护两点间最小 \(xor\) 路径。

在询问 \(u,v\) 中,你可以从 \(u\) 走到 \(t\) 然后走回 \(u\),路径上每条边都被经过两次,所以路径上的边贡献为 \(0\)。因此如果有一条 \(xor\)\(x\)\(u,v\) 路径,有一个 \(xor\)\(c\) 的环,就存在一条 \(xor\)\(x\oplus c\) 的路径。

任意考虑一棵生成树,对于一个非树边 \(u,v,w\),设 \(u\)\(v\) 的树上路径 \(xor\)\(x\),那么存在一个 \(xor\)\(x \oplus w\) 的环,因此如果经过了这条非树边,我们不妨把它看成是沿着树上路径从 \(u\) 走到 \(v\)。之后再异或上这个换的权值。

所以我们只需要考虑把 \(u\)\(v\) 之间的树上路径异或上一些由一条非树边一条树链构成的环的 \(xor\),答案最小是什么。

维护所有非树边加上一条树链构成的环的 \(xor\) 的线性基即可。

然后考虑怎么加边维护这个东西。因为需要回滚,均摊算法(如 LCT,路径压缩的并查集)无法使用。我们只需要支持询问两点是否连通,询问两点之间的 \(xor\),加边和回滚即可。我们可以给点 \(i\) 维护一个值 \(v_i\),初始时所有点的值 \(=0\),用按秩合并的并查集来维护连通性。我们始终要保证对于任意的 \(u,v\),如果 \(u,v\) 连通,那么 \(u,v\) 之间树上路径的 \(xor\) 等于 \(v_u \oplus v_v\)。每次加边的时候,如果两个连通块并成了一个连通块,你可以通过把其中一个连通块内的所有点的 \(v_i\) 异或上一个数来保持这一性质。按秩合并时打个 tag 即可。

时间复杂度为 \(\mathcal O(n \log^2 n)\)

代码

这次尝试了一种新的码风。看上去字符量少了不少。

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200010;

typedef pair<int,int> pi;

int n, m, q;
int eu[maxn*2], ev[maxn*2];
vector<pi> tmp;
int bu[maxn], bv[maxn], bd[maxn], be[maxn];
int qo[maxn], qx[maxn], qy[maxn], qd[maxn], qe[maxn];
int ans[maxn];

namespace DSU {
int f[maxn], d[maxn], w[maxn], e[maxn], top;
int *sta_p[maxn*10], sta_v[maxn*10];
int a[30];
void modify(int &x) {
++ top;
sta_p[top] = &x, sta_v[top] = x;
}
void init() {
for (int i = 1; i <= n; i++) f[i] = i;
}
int gr(int x) {
if (f[x] == x) return x;
return gr(f[x]);
}
int ge(int x) {
if (f[x] == x) return 0;
return e[x] ^ ge(f[x]);
}
int gw(int x) {
return w[x] ^ ge(x);
}
void ins(int x) {
for (int i = 29; i >= 0; i--) {
if (x & (1<<i)) {
if (!a[i]) {
modify(a[i]);
a[i] = x;
break;
} else x ^= a[i];
}
}
}
int ask(int x) {
for (int i = 29; i >= 0; i--) {
if (x & (1<<i)) {
if (a[i]) {
x ^= a[i];
}
}
}
return x;
}
void adde(int u, int v, int x) {
int ru = gr(u), rv = gr(v);
if (ru == rv) {
ins(gw(u) ^ gw(v) ^ x);
} else if (ru != rv) {
if (d[ru] < d[rv]) swap(ru, rv);
modify(f[rv]); f[rv] = ru;
modify(d[ru]); d[ru] = max(d[ru], d[rv] + 1);
modify(e[rv]); e[rv] ^= x ^ gw(u) ^ gw(v);
}
}
void rollb(int t) {
while (top > t) {
(*sta_p[top]) = sta_v[top];
-- top;
}
}
}

int tim = 0;
int vis_l[maxn<<1], vis_r[maxn<<1], _vis[maxn<<1];
int cur_ext[maxn<<1], cur_d[maxn<<1];

void solve(int l, int r) {
int t = DSU::top;
if (l == r) {
if (qo[l] == 3) {
ans[l] = DSU::ask(DSU::gw(qx[l]) ^ DSU::gw(qy[l]));
} else cur_ext[qe[l]] ^= 1;
if (qo[l] == 1) cur_d[qe[l]] = qd[l];
return;
}
int m = (l + r) >> 1;
++ tim;
for (int i = l; i <= m; i++) if (qo[i] != 3) vis_l[qe[i]] = tim;
{
// 准备左区间
for (int i = m+1; i <= r; i++) {
if (qo[i] != 3) {
if (vis_l[qe[i]] != tim) {
if (cur_ext[qe[i]]) {
DSU::adde(eu[qe[i]], ev[qe[i]], cur_d[qe[i]]);
}
}
}
}
solve(l, m);
DSU::rollb(t);
}
++ tim;
for (int i = m+1; i <= r; i++) if (qo[i] != 3) vis_r[qe[i]] = tim;
{
// 准备右区间
for (int i = l; i <= m; i++) {
if (qo[i] != 3) {
if (vis_r[qe[i]] != tim) {
if (cur_ext[qe[i]]) {
DSU::adde(eu[qe[i]], ev[qe[i]], cur_d[qe[i]]);
}
}
}
}
solve(m+1, r);
DSU::rollb(t);
}
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &bu[i], &bv[i], &bd[i]);
if (bu[i] > bv[i]) swap(bu[i], bv[i]);
tmp.push_back(pi(bu[i], bv[i]));
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
scanf("%d", &qo[i]);
if (qo[i] == 1) {
scanf("%d%d%d", &qx[i], &qy[i], &qd[i]);
} else {
scanf("%d%d", &qx[i], &qy[i]);
}
if (qx[i] > qy[i]) swap(qx[i], qy[i]);
if (qo[i] != 3) tmp.push_back(pi(qx[i], qy[i]));
}
sort(tmp.begin(), tmp.end());
for (int i = 1; i <= m; i++) {
be[i] = int (lower_bound(tmp.begin(), tmp.end(), pi(bu[i], bv[i])) - tmp.begin() + 1);
}
for (int i = 1; i <= q; i++) {
if (qo[i] != 3) qe[i] = int (lower_bound(tmp.begin(), tmp.end(), pi(qx[i], qy[i])) - tmp.begin() + 1);
}
for (int i = 0; i < tmp.size(); i++) eu[i+1] = tmp[i].first, ev[i+1] = tmp[i].second;
for (int i = 1; i <= m; i++) cur_ext[be[i]] = 1, cur_d[be[i]] = bd[i];
DSU::init();
for (int i = 1; i <= q; i++) if (qo[i] != 3) _vis[qe[i]] = 1;
for (int i = 1; i <= m; i++) if (!_vis[be[i]]) DSU::adde(bu[i], bv[i], bd[i]);
solve(1, q);
for (int i = 1; i <= q; i++) if (qo[i] == 3) printf("%d\n", ans[i]);
return 0;
}