[Codeforces938G]Shortest Path Queries
给定一个带权无向图,实现三种操作:加边,删边,询问两点间的异或最短路。
\(n, m, q \leq 2\times 10^5\)。
类似最大 xor 和路径,用线性基可以求解异或最短路。
因为线性基删除很麻烦,所以直接离线用线段树分治。
图可能不连通,需要用并查集维护连通性,然后记录每个点到当前根的异或和 \(d_x\)。
加边时设 \(val = d_x\oplus d_y \oplus w\),如果 \(x, y\) 已经联通则将 \(val\) 加入当前联通块的线性基,如果不在一个并查集,连接两个根,边权为 \(val\)。
#include <bits/stdc++.h>
#define perr(a...) fprintf(stderr, a)
#define dbg(a...) perr("\033[32;1m"), perr(a), perr("\033[0m")
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(2e5 + 5);
[N];
PII query#define ls o << 1
#define rs o << 1 | 1
std::vector<std::array<int, 3>> g[N << 2];
void update(int o, int l, int r, int x, int y, int u, int v, int w) {
if (r < x || l > y) return;
if (x <= l && r <= y) {
[o].push_back({u, v, w});
greturn;
}
int m = l + r >> 1;
(ls, l, m, x, y, u, v, w), update(rs, m + 1, r, x, y, u, v, w);
update}
std::vector<std::pair<int*, int>> changes;
void record(int &x) { changes.emplace_back(&x, x); }
void rollBack(size_t t) {
while (changes.size() > t) {
*changes.back().first = changes.back().second;
.pop_back();
changes}
}
int fa[N], siz[N], val[N];
int find(int &x) {
int r = val[x];
while (x != fa[x]) r ^= val[x = fa[x]];
return r;
}
void ins(int *p, int x) {
if (!x) return;
for (int i = 29; i >= 0; i--) {
if (x >> i & 1 ^ 1) continue;
if (!p[i]) {
(p[i]);
record[i] = x;
pbreak;
}
^= p[i];
x }
}
int p[N][30];
void solve(int o, int l, int r) {
size_t now = changes.size();
for (auto [x, y, z] : g[o]) {
int r = find(x) ^ find(y) ^ z;
if (x == y) {
(p[x], r);
ins} else {
if (siz[x] > siz[y]) std::swap(x, y);
(fa[x]), record(siz[y]), record(val[x]);
record[x] = y, siz[y] += siz[x], val[x] ^= r;
fafor (int i = 0; i < 30; i++) ins(p[y], p[x][i]);
}
}
if (l == r) {
auto [x, y] = query[l];
if (x) {
int ans = find(x) ^ find(y);
assert(x == y);
for (int i = 29; i >= 0; i--) smin(ans, ans ^ p[x][i]);
std::cout << ans << "\n";
}
(now);
rollBackreturn;
}
int m = l + r >> 1;
(ls, l, m), solve(rs, m + 1, r);
solve(now);
rollBack}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::map<PII, PII> t;
while (m--) {
int x, y, z;
std::cin >> x >> y >> z;
[PII(x, y)] = {0, z};
t}
std::cin >> m;
for (int i = 1; i <= m; i++) {
int opt, x, y;
std::cin >> opt >> x >> y;
if (opt == 1) {
int z;
std::cin >> z;
[PII(x, y)] = {i, z};
t} else if (opt == 2) {
auto [l, w] = t[PII(x, y)];
(1, 1, m, l, i - 1, x, y, w);
update.erase(PII(x, y));
t} else {
[i] = {x, y};
query}
}
for (auto &[u, v] : t) {
auto &[x, y] = u;
auto &[l, w] = v;
(1, 1, m, l, m, x, y, w);
update}
std::iota(fa, fa + 1 + n, 0);
std::fill(siz, siz + 1 + n, 1);
(1, 1, m);
solvereturn 0;
}
最后修改于 2021-08-13