锐客网

  1. 首页 > it技术 > >

并查集|[CF938G] Shortest Path Queries

线段树并查集图论杂题树状数组

题目描述
【并查集|[CF938G] Shortest Path Queries】给你一幅n个点，m条边的无向图，每条边有权值d，现在有q次操作，有三种操作。
1，给出x,y,d，加入连接x，y的权值为d的边
2，给出x,y，删除这条边
3，给出x,y，问从x到y的路径的最小异或和。
保证操作合法且一直为简单连通图
n,m,q<=1e5
部分分：q=1,且为操作3
解题思路
考虑部分分。
随便搞一个dfs树出来，你一条返祖边代表一个环。x到y的树路径的xor和为x到根的xor和y到根xor的异或和。考虑让环也有贡献，直接搞个环的线性基即可。
操作这么多？
考虑把每条边的存在时间找出来，然后插到以时间为下标线段树的对应节点，发现一条边最多拆成log条。询问就打在线段树叶子上。
dfs一边线段树区间。我们现在想要维护部分分的两个东西，连通性和简单路径xor和用可撤销并查集做，进来区间的时候按秩合并并记录原来的形态，出去的时候撤销即可。线性基由于很小，直接暴力下传。
一条边按秩合并时间复杂度O(logn)，一条原来的边拆成了O(logn)条，时间复杂度O(nlog^2 n)
代码

#include #include #include #include #include #include using namespace std; typedef long long ll; typedef double db; #define fo(i,j,k) for(i=j; i<=k; i++) #define fd(i,j,k) for(i=j; i>=k; i--) #define cmax(a,b) (a=(a>b)?a:b) #define cmin(a,b) (a=(a tr; multiset :: iterator it; int tt,b[M],c[M],val[M],nxt[M],fst[N]; void cr(int x,int y,int z,int t) { tt++; b[tt]=y; c[tt]=z; val[tt]=t; nxt[tt]=fst[x]; fst[x]=tt; } int X,Y,Z; void change(int x,int l,int r,int i,int j) { if (l==i&&r==j) { cr(x,X,Y,Z); return ; } int m=l+r>>1; if (j<=m) change(x*2,l,m,i,j); else if (mrk[ry]) swap(x,y),swap(rx,ry); dl[++td]={rx,Xor[rx],rk[rx],fa[rx]}; dl[++td]={ry,Xor[ry],rk[ry],fa[ry]}; fa[rx]=ry; Xor[rx]=v1^v2^z; if (rk[rx]==rk[ry]) rk[ry]++; } } if (l==r&&qx[l]) { x=qx[l]; y=qy[l]; v1=v2=0; get(x,v1); get(y,v2); prt[l]=calc(base[ax],v1^v2); } if (l!=r) { fo(i,0,29) base[ax*2][i]=base[ax*2+1][i]=base[ax][i]; int m=l+r>>1; solve(ax*2,l,m); solve(ax*2+1,m+1,r); } while (td>tp) { x=dl[td].x; Xor[x]=dl[td].y; rk[x]=dl[td].z; fa[x]=dl[td].t; td--; } } int main() { freopen("t4.in","r",stdin); freopen("t4.out","w",stdout); scanf("%d %d",&n,&m); fo(i,1,m) { scanf("%d %d %d",&x,&y,&z); if (x>y) swap(x,y); tr.insert({x,y,z,1}); } fo(i,1,n) fa[i]=i; scanf("%d",&q); fo(i,1,q) { scanf("%d %d %d",&ka,&x,&y); if (x>y) swap(x,y); if (ka==1) { scanf("%d",&z); tr.insert({x,y,z,i}); }else if (ka==2) { it=tr.lower_bound({x,y,0,0}); X=x; Y=y; Z=(*it).z; change(1,1,q,(*it).t,i); tr.erase(it); }else { qx[i]=x; qy[i]=y; } } while (!tr.empty()) { it=tr.begin(); X=(*it).x; Y=(*it).y; Z=(*it).z; change(1,1,q,(*it).t,q); tr.erase(it); } solve(1,1,q); fo(i,1,q) if (qx[i]) { printf("%d\n",prt[i]); } }

    推荐阅读


    上一篇：算法|[2016/12/1]判断是否存在重复元素 -- c++ set的巧妙用法

    下一篇：DP|[矩阵树定理][prufer序][CF917D]Stranger Trees