CF938G-动态连通图最短xor路（线段树分治、并查集、线性基）

link:https://codeforces.com/contest/938/problem/G

[!Description]
有一张连通的无向图简单图，三种操作：

• 1、加边\((x,y,d)\)
• 2、删边\((x,y)\)
• 3、询问 \(x\to y\) 的路径中异或最小的路径（不一定是简单路径）
• 保证每次操作后图是连通的
  \(1\leq n,m,q\leq 2\times 10^5\).

这题应该可以说是几个算法的大融合，问题很明显比离线的动态图连通性要强，所以基本需要用到线段树分治+并查集，而最小异或则是并查集…

正常分析的话先看3询问，无向图xor最大/最小的路径问题非常经典（之前在另一题里遇到过：https://zhuanlan.zhihu.com/p/577244669），把每个简单环的异或和找出来，插入到线性基里，然后找到一条 \(x\to y\) 的通路的边权，和线性基里的元素找最小值。
那么如何找到一条任意的 \(x\to y\) 的通路呢？就是用xor的性质，带权并查集维护每个点到（并查集上）父节点的边权，按秩合并+路径压缩的并查集可以做到 \(O(\log n)\) 的时间内查询两个点间某条路径的异或和（换成别的可没这么好的性质了），对于删边和加边操作则用线段树分治解决，时间复杂度 \(O(n\log^2 n)\) ：

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define dbg(x) cout<<#x"="<<x<<' '
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> piii;
const int N=2e5+5;
int n,m,q,ans[N];
pii tag[N];
map<pii,pii> lst;
struct DSU{
    int fa[N],sz[N],weight[N],block;
    void init(int n){rep(i,1,n)fa[i]=i,sz[i]=1;block=n;}
    pii find(int x){
        if(fa[x]==x)return {x,0};
        auto [f,d]=find(fa[x]);
        return {f,d^weight[x]};
    }
    int merge(int x,int y,int w){
        auto [fx,dx]=find(x);
        auto [fy,dy]=find(y);
        if(sz[fx]<sz[fy])swap(fx,fy);
        fa[fy]=fx;
        weight[fy]=(w^dx^dy);
        sz[fx]+=sz[fy];
        block--;
        return fy;
    }
    void del(int x){
        if(fa[x]==x)return;
        sz[fa[x]]-=sz[x];
        weight[x]=0;
        fa[x]=x;
        block++;
    }
}dsu;
struct XorBasis{
    int v[30];
    XorBasis(){memset(v,0,sizeof(v));}
    void insert(int x){
        for(int i=29;i>=0;i--)if(x>>i&1){
            if(v[i])x^=v[i];
            else{
                v[i]=x;
                return;
            }
        }
    }
    int work(int w){
        for(int i=29;i>=0;i--)if(w>>i&1)w^=v[i];
        return w;
    }
};
namespace Seg{
    #define ls (node<<1)
    #define rs (node<<1|1)
    stack<pii> S;
    vector<piii> tr[N<<2];
    void insert(int node,int l,int r,int ql,int qr,const piii &v){
        if(ql<=l&&r<=qr){
            tr[node].push_back(v);
            return;
        }
        int mid=(l+r)>>1;
        if(mid>=ql)insert(ls,l,mid,ql,qr,v);
        if(mid+1<=qr)insert(rs,mid+1,r,ql,qr,v);
    }
    void solve(int node,int l,int r,XorBasis lst){
        XorBasis base=lst;
        for(auto [x,y,w]:tr[node]){
            auto [fx,dx]=dsu.find(x);
            auto [fy,dy]=dsu.find(y);
            if(fx==fy)base.insert(w^dx^dy);
            else S.push({node,dsu.merge(x,y,w)});
        }
        if(l==r){
            auto [x,y]=tag[l];
            if(x){
                int d=(dsu.find(x).second^dsu.find(y).second);
                ans[l]=base.work(d);
            }
        }else{
            int mid=(l+r)>>1;
            solve(ls,l,mid,base);
            solve(rs,mid+1,r,base);
        }
        while(!S.empty()&&S.top().first==node){
            dsu.del(S.top().second);
            S.pop();
        }
    }
};
int main(){
    fastio;
    cin>>n>>m;
    dsu.init(n);
    rep(i,1,m){
        int x,y,d;
        cin>>x>>y>>d;
        if(x>y)swap(x,y);
        lst[{x,y}]={0,d};
    }
    cin>>q;
    rep(i,1,q){
        int type,x,y,d;
        cin>>type>>x>>y;
        if(x>y)swap(x,y);
        if(type==1){
            cin>>d;
            lst[{x,y}]={i,d};
        }else if(type==2){
            Seg::insert(1,0,q,lst[{x,y}].first,i-1,{x,y,lst[{x,y}].second});
            lst.erase({x,y});
        }else tag[i]={x,y};
    }
    for(auto [fi,se]:lst){
        auto [x,y]=fi;auto [t,w]=se;
        Seg::insert(1,0,q,t,q,{x,y,w});
    }
    XorBasis base;
    Seg::solve(1,0,q,base);
    rep(i,1,q)if(tag[i].first)cout<<ans[i]<<endl;
    return 0;
}