[CF938G]Shortest|[CF938G]Shortest Path Queries [CF938G]ShortestPathQueries

codeforces
description 【[CF938G]Shortest|[CF938G]Shortest Path Queries】一张无向图，支持如下三种操作：
$1 \ x \ y \ d \$ ：加一条连接$x,y$，边权为$d$的边。
$2xy $：删除$x,y$之间的边。
$3xy $：查询$x$到$y$的异或最短路，也就是异或和最小的一条路径。
保证任意时刻图中无重边无自环，且图连通。
$n,m,q \le 200000$
sol 根据WC2011最大XOR和路径那题的理论，图中两点的异或路径一定是这两点在某棵生成树上的路径异或和再异或上若干个环的异或和。
这题保证图连通，所以这个性质是成立的。
我们考虑动态维护图的连通性。运用线段树分治，以询问为下标建线段树，把每条边放在线段树对应的$\log$个节点上，最终$dfs$整棵线段树计算答案。
在$dfs$的过程中我们需要支持的是维护连通性以及维护路径异或和。
对于一条边$(u,v,w)$，如果$u,v$已经连通，那么就可以往线性基里插入$u,v$的路径异或和异或上$w$的值。否则需要按秩合并$u,v$所在的并查集，同时还需要维护路径异或和。我们对每个点记它到它所在并查集的根的路径异或和，那么每次合并的时候相当于要给其中一个连通块整体异或上一个数。打标记即可。
code

#include #include #include #include #include using namespace std; int gi(){ int x=0,w=1; char ch=getchar(); while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if (ch=='-') w=0,ch=getchar(); while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return w?x:-x; } #define pi pair #define mk make_pair const int N = 2e5+5; struct edge{int u,v,w,l,r; }E[N<<1]; struct query{int u,v; }q[N]; struct mdf{int x,y,sz; }s[N<<1]; int n,m,tot,fa[N],sz[N],tag[N],top; vectorv[N<<2]; mapM; struct xxj{ int p[31]; void insert(int x){ for (int j=30; ~j; --j) if ((x>>j)&1){ if (!p[j]) {p[j]=x; return; } x^=p[j]; } } int calc(int x){ for (int j=30; ~j; --j) x=min(x,x^p[j]); return x; } }tmp; void modify(int x,int l,int r,int ql,int qr,int i){ if (l>=ql&&r<=qr) {v[x].push_back(i); return; } int mid=l+r>>1; if (ql<=mid) modify(x<<1,l,mid,ql,qr,i); if (qr>mid) modify(x<<1|1,mid+1,r,ql,qr,i); } int getf(int x){ while (x!=fa[x]) x=fa[x]; return x; } int getd(int x){ int d=0; while (x!=fa[x]) d^=tag[x],x=fa[x]; return d; } void dfs(int x,int l,int r,xxj S){ int tt=top; for (auto i:v[x]){ int x=getf(E[i].u),y=getf(E[i].v),dx=getd(E[i].u),dy=getd(E[i].v); if (x==y) {S.insert(dx^dy^E[i].w); continue; } if (sz[x]>sz[y]) swap(x,y),swap(dx,dy); s[++top]=(mdf){x,y,sz[y]}; fa[x]=y; sz[y]+=sz[x]; tag[x]=dx^dy^E[i].w; } if (l==r){ int dx=getd(q[l].u),dy=getd(q[l].v); printf("%d\n",S.calc(dx^dy)); }else{ int mid=l+r>>1; dfs(x<<1,l,mid,S); dfs(x<<1|1,mid+1,r,S); } while (top>tt){ int x=s[top].x,y=s[top].y; tag[x]=0; fa[x]=x; sz[y]=s[top].sz; --top; } } int main(){ n=gi(); m=gi(); for (int i=1; i<=m; ++i){ int u=gi(),v=gi(),w=gi(); if (u>v) swap(u,v); E[i]=(edge){u,v,w,1,-1}; M[mk(u,v)]=i; } int Case=gi(); while (Case--){ int op=gi(); if (op==1){ int u=gi(),v=gi(),w=gi(); if (u>v) swap(u,v); E[++m]=(edge){u,v,w,tot+1,-1}; M[mk(u,v)]=m; }else if (op==2){ int u=gi(),v=gi(); if (u>v) swap(u,v); E[M[mk(u,v)]].r=tot; M.erase(mk(u,v)); }else{ int u=gi(),v=gi(); q[++tot]=(query){u,v}; } } for (int i=1; i<=m; ++i){ if (E[i].r==-1) E[i].r=tot; if (E[i].l<=E[i].r) modify(1,1,tot,E[i].l,E[i].r,i); } for (int i=1; i<=n; ++i) fa[i]=i,sz[i]=1; dfs(1,1,tot,tmp); return 0; }

转载于:https://www.cnblogs.com/zhoushuyu/p/9433627.html