【CF938G】Shortest Path Queries（线段树分治，并查集，线性基）
题面
题解
吼题啊。
对于每个边，我们用一个(map)维护它出现的时间，
发现询问单点，边的出现时间是区间，所以线段树分治。
既然路径最小值就是异或最小值，并且可以不是简单路径，
不难让人想到(WC2011)那道最大(Xor)路径和。
用一样的套路，我们动态维护一棵生成树，碰到一个非树边，
就把这个环的异或和丢到线性基里面去，这样子直接查就好了。
动态维护生成树直接用并查集就好了，没有必要(LCT)
大概就是永远不进行路径压缩，每次启发式合并。
询问的时候暴跳父亲。
然后撤销操作的话，维护一个栈，每次存下当前的修改操作，
撤销的时候倒序还原就好了。
细节很多，第一次写这样的东西，调了好久啊。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define MAX 200200
#define ll long long
#define pi pair<int,int>
#define mp(x,y) make_pair(x,y)
#define lson (now<<1)
#define rson (now<<1|1)
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
struct xxj
{
int p[31];
void insert(int x)
{
for(int i=30;~i;--i)
if(x&(1<<i))
{
if(!p[i]){p[i]=x;break;}
x^=p[i];
}
}
int Query(int x){for(int i=30;~i;--i)x=min(x,x^p[i]);return x;}
}G;
struct Node{int u,v,w;}p[MAX<<1];
pi q[MAX];
int n,m;
map<pi,int> M;
vector<Node> seg[MAX<<2];
void Modify(int now,int l,int r,int L,int R,Node e)
{
if(L>R)return;if(L<=l&&r<=R){seg[now].push_back(e);return;}
int mid=(l+r)>>1;
if(L<=mid)Modify(lson,l,mid,L,R,e);
if(R>mid)Modify(rson,mid+1,r,L,R,e);
}
int tim,cnt,L[MAX<<1],R[MAX<<1];
int f[MAX],sz[MAX],Xor[MAX];
int getf(int x){while(x!=f[x])x=f[x];return x;}
int getxor(int x){int ret=0;while(x!=f[x])ret^=Xor[x],x=f[x];return ret;}
void Divide(int now,int l,int r,xxj G)
{
vector<Node> c;c.clear();
for(int i=0,lim=seg[now].size();i<lim;++i)
{
int u=seg[now][i].u,v=seg[now][i].v,w=seg[now][i].w;
int f1=getf(u),f2=getf(v);
if(f1==f2)G.insert(getxor(u)^getxor(v)^w);
else
{
if(sz[f1]>sz[f2])swap(f1,f2),swap(u,v);
w^=getxor(v)^getxor(u);
c.push_back((Node){f1,f2,sz[f2]});
Xor[f1]=w;f[f1]=f2;sz[f2]+=sz[f1];
}
}
if(l==r)
printf("%d
",G.Query(getxor(q[l].first)^getxor(q[l].second)));
else
{
int mid=(l+r)>>1;
Divide(lson,l,mid,G);Divide(rson,mid+1,r,G);
}
for(int i=c.size()-1;~i;--i)
{
int u=c[i].u,v=c[i].v,w=c[i].w;
sz[v]=w;f[u]=u;Xor[u]=0;
}
}
int main()
{
//freopen("938G.in","r",stdin);
//freopen("938G.out","w",stdout);
n=read();m=read();
for(int i=1;i<=m;++i)
{
int x=read(),y=read(),w=read();
p[++cnt]=(Node){x,y,w};
L[cnt]=1;M[mp(x,y)]=cnt;R[cnt]=-1;
}
int Q=read();
for(int i=1;i<=Q;++i)
{
int opt=read(),x=read(),y=read();
if(x>y)swap(x,y);
if(opt==1)
{
p[++cnt]=(Node){x,y,read()};
L[cnt]=tim+1;R[cnt]=-1;M[mp(x,y)]=cnt;
}
else if(opt==2)R[M[mp(x,y)]]=tim;
else q[++tim]=mp(x,y);
}
for(int i=1;i<=cnt;++i)if(R[i]==-1)R[i]=tim;
for(int i=1;i<=cnt;++i)Modify(1,1,tim,L[i],R[i],p[i]);
for(int i=1;i<=n;++i)f[i]=i,sz[i]=1;
Divide(1,1,tim,G);
return 0;
}