worldpress 建站,小程序开发平台免费,上海网站建设收费标准,商用自适应网站建设CF938G Shortest Path Queries
Solution
套路题。 xorxorxor最短路可以用线性基维护#xff08;把每个环的边权异或和放进线性基#xff0c;询问时把树边路径边权异或和放在线性基里跑出最小值即可#xff09;。
然后因为线性基删除比较慢而麻烦#xff08;注意线性基是…CF938G Shortest Path Queries
Solution
套路题。
xorxorxor最短路可以用线性基维护把每个环的边权异或和放进线性基询问时把树边路径边权异或和放在线性基里跑出最小值即可。
然后因为线性基删除比较慢而麻烦注意线性基是有办法动态加删元素的因此动态加删边可以用线段树分治可撤销带权并查集实现。
时间复杂度O(nlg2n)O(nlg^2n)O(nlg2n)。
Code最近顺便改了改码风
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename T inline bool upmin(T x, T y) { return y x ? x y, 1 : 0; }
templatetypename T inline bool upmax(T x, T y) { return x y ? x y, 1 : 0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint, int PR;
typedef vectorint VI;const lod eps 1e-11;
const lod pi acos(-1);
const int oo 1 30;
const ll loo 1ll 62;
const int mods 998244353;
const int MAXN 1000005;
const int INF 0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f 1, x 0; char c getchar();while (c 0 || c 9) { if (c -) f -1; c getchar(); }while (c 0 c 9) { x (x 3) (x 1) (c ^ 48); c getchar(); }return x * f;
}
mapPR, PR Map;
int n, m, base[30], btop 0, bstk[MAXN], f[MAXN], num[MAXN], d[MAXN], Ans[MAXN], utop 0;
struct ustknode{ int u, v, c; } ustk[MAXN];
struct Cnode{ int x, y, c; };
struct Qnode{ int id, x, y; };
vectorCnode C[MAXN];
vectorQnode Q[MAXN]; void insert(int x) {for (int i 29; i 0; -- i)if ((x i) 1) {if (!base[i]) { base[i] x, bstk[btop] i; return; }x ^ base[i];}
}
int getmn(int x) {for (int i 29; i 0; -- i) upmin(x, x ^ base[i]);return x;
} int find(int x) { return f[x] x ? f[x] : find(f[x]); }
int getdis(int x) { return f[x] x ? d[x] : getdis(f[x]) ^ d[x]; }
void unions(int u, int v, int c) {if (num[u] num[v]) swap(u, v);ustk[utop] (ustknode){u, v, c}, f[v] u, d[v] ^ c, num[u] num[v];
}
void update(int x, int l, int r, int L, int R, Cnode y)
{if (l L r R) { C[x].PB(y); return; }int mid (l r) 1;if (R mid) update(x 1, l, mid, L, R, y);else if (L mid) update(x 1 | 1, mid 1, r, L, R, y);else update(x 1, l, mid, L, mid, y), update(x 1 | 1, mid 1, r, mid 1, R, y);
}
void solve(int x, int l, int r) {int blst btop, ulst utop;for (auto t:C[x]) {int u t.x, v t.y, c t.c, uu find(u), vv find(v);if (uu vv) insert(getdis(u) ^ getdis(v) ^ c);else unions(uu, vv, getdis(u) ^ getdis(v) ^ c); }if (l r) {for (auto t:Q[l]) Ans[t.id] getmn(getdis(t.x) ^ getdis(t.y));}else {int mid (l r) 1;solve(x 1, l, mid);solve(x 1 | 1, mid 1, r);}while (btop blst) base[bstk[btop --]] 0;while (utop ulst) num[ustk[utop].u] - num[ustk[utop].v], f[ustk[utop].v] ustk[utop].v, d[ustk[utop].v] ^ ustk[utop].c, -- utop;
}
signed main() {n read(), m read();for (int i 1; i n ; i) num[i] 1, f[i] i;for (int i 1; i m ; i) {int u read(), v read(), c read();Map[MP(u, v)] MP(0, c);}int Case read(), num 0;for (int i 1; i Case ; i) {int opt read(), x read(), y read(), c;if (opt 1) c read(), Map[MP(x, y)] MP(i, c);if (opt 2) update(1, 0, m, Map[MP(x, y)].fi, i, (Cnode){x, y, Map[MP(x,y)].se}), Map.erase(MP(x, y));if (opt 3) Q[i].PB(((Qnode){ num, x, y} ));}for (auto t : Map) update(1, 0, m, t.se.fi, m, (Cnode){t.fi.fi, t.fi.se, t.se.se});solve(1, 0, m);for (int i 1; i num; i) printf(%d\n, Ans[i]);return 0;
}
