CF 938 G Shortest Path Queries

CF 938 G Shortest Path Queries

看到 XOR 最短路就可以想到 WC 最长XOR路径的做法,也就是把环都给丢进线性基里面,查询就查路径 XOR 值在 线性基能 XOR 出的最小值。

如果只有插入怎么做?插入的时候维护一下与 生成树 形成的环就好了。

可是现在不仅有了插入,还有删除。发现线性基这个东西不太好删除,于是可以按时间分治(线段树分治),维护每个边存在的时间段,最后 dfs 一次时间线段树解决问题。

但是既然有删除的存在,就必然存在图不联通的情况,而且删除也可能删除树上的边。所以我们还得想办法动态维护树的形态。 LCT 自然可以,但是太麻烦了。我们要查询的东西是一个点到根的路径的 XOR ,要支持插入点,回滚,这明显可以用可撤销并查集来做。于是用并查集维护一下就完了。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m , q;
vector<pii> G[MAXN];
int a[31];
void ins( int x ) {
    for( int i = 30 ; i >= 0 ; -- i ) if( x & ( 1 << i ) ) {
        if (!a[i]) { a[i] = x;return; }
        x ^= a[i];
    }
}
int chkmn( int* p , int x ) {
    for( int i = 30 ; i >= 0 ; -- i ) if( x > ( x ^ p[i] ) )
        x = ( x ^ p[i] );
    return x;
}

vector<pair<pii,int>> E[MAXN << 2];
void inse( int rt , int l , int r , int L , int R , pair<pii,int> e ) {
    if( L <= l && R >= r ) { E[rt].pb( e ); return; }
    int m = l + r >> 1;
    if( L <= m ) inse( rt << 1 , l , m , L , R , e );
    if( R > m ) inse( rt << 1 | 1 , m + 1 , r , L , R , e );
}
pii Q[MAXN]; int ans[MAXN];

int fa[MAXN] , f[MAXN] , dep[MAXN];
int getfa( int u ) { return u == fa[u] ? u : getfa( fa[u] ); }
int getdis( int u ) { return u == fa[u] ? 0 : f[u] ^ getdis( fa[u] ); }

void work( int rt , int l , int r ) {
    int ta[31];
    memcpy( ta , a , sizeof a );
    vector<pair<pii,int>> vec;
    for( auto& t : E[rt] ) {
        int u = t.fi.fi , v = t.fi.se , w = t.se;
        int fu = getfa( u ) , fv = getfa( v );
        w ^= getdis( u ) ^ getdis( v );
        if( fu == fv ) ins( w );
        else {
            if( dep[fu] > dep[fv] ) swap( fu , fv ) , swap( u , v );
            vec.eb( mp( mp( fu , fv ) , 0 ) );
            fa[fu] = fv , f[fu] = w;
            if( dep[fu] == dep[fv] ) ++ dep[fv] , vec.rbegin() -> se = 1;
        }

    }
    int m = l + r >> 1;
    if( l == r )
        ans[l] = chkmn( a , getdis( Q[l].fi ) ^ getdis( Q[l].se ) );
    else work( rt << 1 , l , m ) , work( rt << 1 | 1 , m + 1 , r );
    reverse( all( vec ) );
    for( auto& t : vec ) {
        fa[t.fi.fi] = t.fi.fi;
        f[t.fi.fi] = 0;
        dep[t.fi.se] -= t.se;
    }
    memcpy( a , ta , sizeof a );
}
pair<pii,int> ed[MAXN];
set<pair<pii,int>> cur;
map<pair<pii,int>,int> tim;
void solve() {
//    freopen("input","r",stdin);
    cin >> n >> m;
    rep( i , 1 , n ) fa[i] = i;
    for( int i = 1 , u , v , x ; i <= m ; ++ i ) {
        scanf("%d%d%d",&u,&v,&x);
        G[u].eb( mp( v , x ) ) , G[v].eb( mp( u , x ) );
        ed[i] = mp( mp( u , v ) , x );
    }
    for( int i = 1 ; i <= m ; ++ i ) {
        int u = ed[i].fi.fi , v = ed[i].fi.se;
        cur.insert( ed[i] ) , tim[ed[i]] = 0;
    }
    cin >> q;
    int opt , u , v , d;
    pair<pii,int> qwq;
    vi ques;
    for( int i = 1 ; i <= q ; ++ i ) {
        scanf("%d%d%d",&opt,&u,&v);
        if( opt == 1 ) {
            scanf("%d",&d);
            qwq = mp( mp( u , v ) , d );
            tim[qwq] = i;
            cur.insert( qwq );
        } else if( opt == 2 ) {
            qwq = mp( mp( u , v ) , 0 );
            auto t = tim.lower_bound( qwq );
            cur.erase( qwq );
            inse( 1 , 0 , q + 1 , t -> se , i , t -> fi );
            tim.erase( t );
        } else {
            Q[i] = mp( u , v ); ques.pb( i );
        }
    }
    for( auto& x : tim ) inse( 1 , 0 , q + 1 , x.se , q + 1 , x.fi );
    work( 1 , 0 , q + 1 );
    for( int x : ques ) printf("%d\n",ans[x]);
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}
\