JZTXT

CF938G Shortest Path Queries 题解

发布时间 2023-07-27 12:27:55作者: adolf_stalin

目录

题目链接

CF938G
洛谷挂了 只能交CF

题目分析

本题有以下几个关键点：

为什么使用生成树建树

首先 根据 \(WC2011\) 我们发现可以使用 \(dfs\) 序来保存节点之间的关系
但是我们发现 本题目中存在加边 删边操作 不适合使用 \(dfs\) 序。
但是，生成树支持这一点。我们只需要在添加这条边的时候进行对环贡献的拆解就可以。

对于异或贡献的分析

由于使用了可撤销并查集，我们在使用生成树边时候并不是针对 \((u,v,w)\) 建边，而是对 \((fa[u],fa[v],w')\) 建边。
为了使两者等价，我们不得不提前计算 \(w\) 对图新产生的贡献
然后在建边时，使用新的权值建边。
计算方式由 \(dis[i]\) 的定义产生影响：

dis[i] 表示 i 点到祖先的异或距离

所以，我们考虑如下的求新边权方式：

inline int get_fa(int x){
	if(x == f[x])	return 0 ;
	return dis[x] ^ get_fa(f[x]) ;
}

令 \(x , y\) 表示为两端节点的祖先
最后的新边权表示为：

\[w_i=dis_x^{\wedge}dis_y^{\wedge}w_i \]

注意最后的答案 是祖先分别到 \(u , v\) 的贡献，中间还要在异或一下。

code

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<cstring>
using namespace std ;
#define ll long long
const int MAXN = 2e5+10 ;
struct Edge{
	int to ,from ,w ;
}edge[MAXN << 1] ;
map<ll , int>	mapp ;
int ans[MAXN][3] ;
vector<ll> que[MAXN<<2] ;
vector<ll> upd[MAXN<<2] ;//开线段树大小 
int ask[MAXN] ,rk[MAXN] ,t[MAXN<<1] ,f[MAXN] ,dis[MAXN] ,len ,s[MAXN<<1] ;

inline void modify1(int node , int li , int ri , int l , int r , int id){
	if(li > r || ri < l)	return ;
	if(l <= li && ri <= r){
		upd[node].push_back(id) ;//是新边，编号为1~len，放在node节点上 
		return ;
	}
	int mid = li + ri >> 1 ;
	modify1(node << 1 , li , mid , l , r , id) ;
	modify1(node << 1 | 1 , mid+1 , ri , l , r , id) ;
}

inline void modify2(int node , int li , int ri , int x , int id){
	if(li > x || ri < x)	return ;
	if(li == ri){
		que[node].push_back(id) ;//等待查询的队列中 
		return ;
	} 
	int mid = li + ri >> 1 ;
	modify2(node << 1 , li , mid , x , id) ;
	modify2(node << 1 | 1 , mid+1 , ri , x , id) ;
}

inline void ins(int x , int *p){//插入线性基 
	for(int i = 29;i >= 0;--i)
		if(x & (1 << i)){
			if(p[i] == 0){
				p[i] = x ;
				return ;
			}else{
				x ^= p[i] ;
			}	
		}
}

inline int query(int val ,int *p){//寻找最小xor和 
	int ans = val ;
	for(int i = 29;i >= 0;--i){
		ans = min(ans , ans ^ p[i]) ;
	}
	return ans ;
}

inline int findd(int x){
	return x== f[x] ? x : findd(f[x]) ;
}

inline int get_fa(int x){//找到从祖先到当前节点的异或和，从而可以确定要建新边的权值 
	if(x == f[x])	return 0 ;
	return dis[x] ^ get_fa(f[x]) ;
}

int tp ;
int px[MAXN] ,pd[MAXN] ,pr[MAXN] ;
inline int update(int node , int *p){
	int siz = 0 ;
	for(int i = 0;i < upd[node].size();++i){
		int id = upd[node][i] ;//加边操作编号 
		int u = edge[id].from ,v = edge[id].to ,w = edge[id].w ;
		int x = findd(u) ,y = findd(v) ;
		w ^= (get_fa(u) ^ get_fa(v)) ;//计算dis[i]:两端的祖先节点异或上本边权 
		//为什么不是父亲节点？因为在并查集里我们实际上建边的是x与y而非u与v 
		if(rk[x] > rk[y])	swap(x , y) ;//按秩合并 
		if(x != y){//是生成树中新的边 
			tp++ ;
			px[tp] = x ;//在栈里面储存要加边的点的信息以便删除 
			pd[tp] = dis[x] ;
			dis[x] = w ;//加边 
			f[x] = y ;	
			pr[tp] = rk[y] ;
			if(rk[x] == rk[y])	rk[y]++ ;//按秩合并 
			siz++ ;
		}else{//产生环，放入线性基 
			ins(w , p) ;
		}
	}
	return siz ;
}

inline void clear(int node , int siz){//撤销并查集操作 
	while(siz--){
		int x = px[tp] ,y = f[x] ;
		f[x] = x ;
		dis[x] = pd[tp] ;
		rk[y] = pr[tp] ;
		tp-- ;
	}
}

inline void solve(int node , int l , int r , int *p){
	int siz = update(node , p) ;//查询前先更新一下 设置好当前环境下边的状态 
	if(l == r){
		for(int i = 0;i < que[node].size();++i){//由于查询的时候是按照时间点查询的，所以不会产生一次询问分裂成两个节点的情况 
			int id = que[node][i] ; 
			ask[id] = query(get_fa(ans[id][1]) ^ get_fa(ans[id][2]) , p) ;//基础的必需值和线性基增加的环值贡献 
		}
		clear(node , siz) ;
		return ;
	}
	int mid = l + r >> 1 ;
	int h[30] ;
	for(int i = 0;i <= 29;++i)	h[i] = p[i] ;
	solve(node << 1 , l , mid , p) ; 
	for(int i = 0;i <= 29;++i)	h[i] = p[i] ;//重置p[]数组 
	solve(node << 1 | 1 , mid+1 , r , p) ;
	clear(node , siz) ;//撤销 
}

int main(){
	ll n ,m ,q ;
	scanf("%lld%lld" , &n , &m) ;
	for(int i = 1;i <= m;++i){
		ll u ,v ,w ;
		scanf("%lld%lld%lld" , &u , &v , &w) ;
		if(u > v)	swap(u , v) ;//保证后面的map[]映射正确 
		mapp[u * n + v] = i ;
		edge[i].from = u ;
		edge[i].to = v ;
		edge[i].w = w ;
		s[i] = 1 ;
	}
	len = m ;
	scanf("%lld" , &q) ;
	int tim = 1 ,tot = 0 ;
	for(int i = 1;i <= q;++i){
		long long opt ,u ,v ,w ;
		scanf("%lld%lld%lld" , &opt , &u , &v) ;
		if(u > v)	swap(u , v) ;
		if(opt == 1){
			scanf("%lld" , &w) ;
			mapp[n * u + v] = ++len ;//第len号新边 
			edge[len].from = u ,edge[len].to = v ,edge[len].w = w ;//重新加入这条边 
			s[len] = ++tim ;//在第tim号时间时发生 
		}else if(opt == 2){
			t[mapp[u * n + v]] = tim++ ;//此时这条边删除（tim时刻还存在） 
		}else{//一次询问操作 
			tot++ ;
			ans[tot][0] = tim ;
			ans[tot][1] = u ;
			ans[tot][2] = v ;
		}
	}
	for(int i = 1;i <= len;++i){
		if(t[i] == 0)	t[i] = tim ;//默认一直存在 
		modify1(1 , 1 , tim , s[i] , t[i] , i) ;//统一加边 
	}
	for(int i = 1;i <= tot;++i)	modify2(1 , 1 , tim , ans[i][0] , i) ;//统一询问 
	for(int i = 1;i <= n;++i)	f[i] = i ,dis[i] = 0 ,rk[i] = 1 ;
	int p[30] ;
	memset(p , 0 , sizeof p) ;
	for(int i = 1;i <= tot;++i)	ask[i] = 1 << 30 ;//将ans[]更新为最大值 来求min 
	solve(1 , 1 , tim , p) ;//统一解决 
	for(int i = 1;i <= tot;++i)	printf("%d\n" , ask[i]) ;
	return 0 ;
}