526互联

luogu P3733 [HAOI2017] 八纵八横 题解【线段树分治+线性基+可撤销并查集+bitset】

发布时间 2023-07-29 16:31:25作者: adolf_stalin

目录

题目大意

题目链接

给出一张 \(n\) 个点 \(m\) 条边的连通无向图，边带边权 \(w_i\) 。有以下三种操作，共 \(q\) 次：
\(\centerdot\)在点 \(x,y\) 之间加入一条边权为\(w_i\)的边，如果这是第\(i\)个此种操作，则记这条新边为第\(i\)条。
\(\centerdot\)将第\(k\)条新边权值改为\(w_i\) 。
\(\centerdot\)删掉第\(k\)条新边，保证这条边之后不会再出现。
对于初始状态和每次操作后，从图中找到一条从\(1\)出发，并回到\(1\) 的一条权值最大路径，路径权值定义为经过边边权的异或和。点边均可多次经过，边经过多次边权也会被计算多次。
(\(1\leqslant n,m \leqslant 500,1\leqslant q,\log_2w_i\leqslant 10^3\),加边操作不超过 \(550\)次)

解题思路

首先发现可以任意获取一个环。也就是说，获取一个环的代价为零。
那么我们可以考虑以下几个步骤：

  1. 找到所有的环。
  2. 计算对于每个环取或不取的最大值。
  3. 修改环的存在。

首先感性理解：如果一个环的所有边中只有一条非树边，那么我们称其为简单环；针对所有的非简单环，我们都可以利用几个简单环拼成非简单环。
那么我们只需要考虑所有的简单环即可。而这个操作可以使用可撤销并查集和线性基实现。具体题目见P4151 [WC2011] 最大XOR和路径 。
那么本题的关键点就是如何修改线性基的环。
考虑到既有添加操作，又有删除操作，不妨使用离线算法线段树分治。
记得进行并查集撤销的时候需要清除干净。
同时进行异或操作的时候可以使用std::bitset 优化时间复杂度。

code

#include<iostream>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cstring>
using namespace std ;

const int MAXN = 2e3+10 ;
struct Edge{
	int from ,to ;
	bitset<MAXN> w ;
}edge[MAXN] ;
char opt[10] ;
int stack[MAXN] ,top ;

inline void get_bit(bitset<MAXN> &x){
	char str[MAXN] ;
	x.reset() ;
	scanf("%s" , str) ;
	int len = strlen(str) ;
	for(int i = 0;i < len;++i)	if(str[i] == '1')	x.set(len - i - 1) ;	
}

inline void print(const bitset<MAXN> &x){
	int flag = 0; if (x.none()) return putchar('0'), void();
    for (int i = MAXN - 1; ~i; --i)
        if (flag && x[i] == 0) putchar('0');
        else if (x[i] == 1) putchar('1'), flag = 1;
}

struct Linear_basis{
	bitset<MAXN> c[MAXN] ;
	int lbsta[MAXN] ,lbtp ;
	inline void insert(bitset<MAXN> x){
		for(int i = MAXN-1;i >= 0;--i){
			if(x[i]){
				if(c[i].none()){
					lbsta[++lbtp] = i ;
					c[i] = x ;
					return ;
				}else{
					x ^= c[i] ;
				}
			}
		}
	}
	
	inline void del(int pos){
		while(lbtp != pos){
			c[lbsta[lbtp]].reset() ;
			lbtp-- ;
		}
	}
	
	inline bitset<MAXN> query(){
		bitset<MAXN> ret ;
		for(int i = MAXN-1;i >= 0;--i){
			if(ret[i] == 0){//不存在当前值，说明可以更大 
				if(c[i].any())	ret ^= c[i] ;
			}
		}
		return ret ;
	}
}lb ;

struct DSU{
	int fa[MAXN] ,siz[MAXN] ;
	bitset<MAXN> dis[MAXN] ;
	struct mem{
		int x ,y ,s ;
	}sta[MAXN] ;
	int topp ;
	
	inline void init(int n){
		for(int i = 1;i <= n;++i)	fa[i] = i ,siz[i] = 1 ; 
	}
	
	inline int findd(int x){
		return x == fa[x] ? x : findd(fa[x]) ;
	}
	
	inline bitset<MAXN> finddis(int x){
		return x == fa[x] ? dis[x] : dis[x] ^ finddis(fa[x]) ; 
	}
	
	inline void merge(Edge x){
		int u = x.from ,v = x.to ;
		bitset<MAXN> w = x.w ;
		if(findd(u) == findd(v)){
			lb.insert(finddis(u) ^ finddis(v) ^ w) ;
			return  ;
		}
		if(siz[findd(u)] > siz[findd(v)])	swap(u , v) ;
		sta[++topp] = mem{findd(u) , findd(v) , siz[findd(v)]} ;
		siz[findd(v)] += siz[findd(u)] ;
		dis[findd(u)] = finddis(u) ^ finddis(v) ^ w ;
		fa[findd(u)] = findd(v) ;
	}
	
	inline void del(int pos){
		while(topp != pos){
			fa[sta[topp].x] = sta[topp].x ;
			siz[sta[topp].y] -= siz[sta[topp].x] ;
			dis[sta[topp].x] = 0 ;
			topp-- ;
		}
	}
}dsu ;

struct Segtree{
	struct Node{
		vector<Edge>	e ;
		int l ,r ;
	}tree[MAXN << 2] ;
	
	inline void build(int node , int l , int r){
		tree[node].l = l ,tree[node].r = r ;
		if(l == r)	return ;
		int mid = (l + r) >> 1 ;
		build(node << 1 , l , mid) ;
		build(node << 1 | 1 , mid+1 , r) ;
	}
	
	inline void update(int node , int l , int r , Edge v){
		if(l <= tree[node].l && tree[node].r <= r){
			tree[node].e.push_back(v) ;
			return ;
		}
		int mid = (tree[node].l + tree[node].r) >> 1 ;
		if(l <= mid)	update(node << 1 , l , r , v) ;
		if(mid < r)	update(node<<1|1 , l , r , v) ;
	}
	
	inline void query(int node){
		int mem1 = lb.lbtp ;
		int mem2 = dsu.topp ;
		for(auto v: tree[node].e)	dsu.merge(v) ;
		if(tree[node].l == tree[node].r)	print(lb.query()) ,printf("\n") ;
		else query(node << 1) ,query(node << 1 | 1) ;
		lb.del(mem1) ,dsu.del(mem2) ;
	}
}seg ;

int main(){
	int n ,m ,p ;
	scanf("%d%d%d" , &n , &m , &p) ;
	bitset<MAXN> w ;
	seg.build(1 , 0 , p) ;
	dsu.init(n) ;
	for(int i = 1;i <= m;++i){
		int u ,v ;
		scanf("%d%d" , &u , &v) ;
		get_bit(w) ;
		seg.update(1 , 0 , p , Edge{u , v , w}) ;
	}
	for(int i = 1;i <= p;++i){
		scanf("%s" , opt) ;
		if(opt[0] == 'A'){
			int u ,v ;
			scanf("%d%d" , &u , &v) ;
			get_bit(w) ;
			edge[++top] = Edge{u , v , w} ;
			stack[top] = i ;
		}else{
			int k ;
			if(opt[1] == 'a'){
				scanf("%d" , &k) ;
				seg.update(1 , stack[k] , i-1 , edge[k]) ;
				stack[k] = 0 ;
			}else{
				scanf("%d" , &k) ;
				get_bit(w) ;
				seg.update(1 , stack[k] , i-1 , edge[k]) ;
				stack[k] = i ;
				edge[k].w = w ;
			}
		}
	}
	for(int i = 1;i <= top;++i)	if(stack[i])	seg.update(1 , stack[i] , p , edge[i]) ;
	seg.query(1) ; 
	return 0 ;
}