环异或 + bitset线性基 +线段树分治 ： P3733

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135240352

https://www.luogu.com.cn/problem/P3733

包括首都的环肯定由一个生成树上一堆环并起来，也就是对于一棵生成树，我们把所有非树边对应的环丢入线性基中，然后求最大。

由于初始的图不变，所有生成树就可以不变了。

对于加边、删边、改边操作。改边相当于删+加。每条边有一个存活时间，显然线段树分治即可。

线性基要写bitset优化。

1
2
3
4
5
pre coding at 9:43
st coding at 9:56
st bugging at 10:50
passing at 10:59
fn blogging at 11:04
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 4010
void print(bitset<N>s) {
	int i; 
	for(i=N-1; i>=0; --i) if(s[i]) break; 
	for(; i>=0; --i) printf("%d", s[i] ? 1 : 0); puts(""); 
}
//#define M
//#define mo
struct EV { int u, v; bitset<N>z; }a[N<<1]; vector<EV>Ev; 
vector<pair<int, bitset<N> > >G[N]; 
int n, m, i, j, k, T, q, f[N], u, v;
int tot, tot2; 
int Begin[N<<1], End[N<<1], Real[N<<1]; 
bitset<N>Z, dis[N]; 
string str; 

struct vector_space { 
	int i; 
	bitset<N>p[N]; 
	void add(bitset<N> k) {
		for(i=1000; i>=0; --i) 
			if(k[i]) {
				if(p[i].count()==0) { p[i]=k; break; }
				k^=p[i]; 
			}
	}
	bitset<N> qmx() {
		bitset<N> ans=0; 
		for(i=1000; i>=0; --i) 
			if(p[i][i] && !ans[i]) ans=(ans^p[i]); 
		return ans; 
	}
}fo;

struct Segment_tree {
	#define ls (k<<1)
	#define rs (k<<1|1)
	#define mid ((l+r)>>1) 
	vector<bitset<N> >G[N<<2]; 
	void add(int k, int l, int r, int x, int y, bitset<N>z) {
		if(l>=x && r<=y) return G[k].pb(z), void();   
		if(x <= mid) add(ls, l, mid, x, y, z); 
		if(y >= mid+1) add(rs, mid+1, r, x, y, z); 
	}
	void que(int k, int l, int r, vector_space z) {
		for(auto t : G[k]) z.add(t); 
		if(l==r) return print(z.qmx()), void(); 
		que(ls, l, mid, z); que(rs, mid+1, r, z); 
	}
	#undef ls
	#undef rs
	#undef mid
}Seg;

int fa(int x) {
	if(f[x] == x) return x; 
	return f[x] = fa(f[x]); 
}

void dfs(int x, int fa) {
	for(auto t : G[x]) {
		int y = t.fi; 
		if(y == fa) continue; 
		dis[y] = dis[x] ^ t.se; 
		dfs(y, x); 
	}
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); q=read(); 
	for(i=1; i<=n; ++i) f[i]=i; 
	for(i=1; i<=m; ++i) {
		u=read(); v=read(); cin>>Z; 
		if(fa(u) == fa(v)) Ev.pb({u, v, Z}); 
		else { f[fa(u)] = fa(v); G[u].pb({v, Z}); G[v].pb({u, Z}); }
	}
	dfs(1, 0); 
//	for(i=1; i<=n; ++i) { debug("%d : ", i); print(dis[i]); }
	for(auto t : Ev) fo.add(dis[t.u]^dis[t.v]^t.z); 
	print(fo.qmx()); 
	if(!q) return 0; 
	tot2 = q; 
	for(i=1; i<=q; ++i) {
		cin>>str; 
		if(str == "Add") {
			++tot; 
			a[tot].u=read(); a[tot].v=read(); cin>>a[tot].z; 
			Real[tot]=tot; Begin[Real[tot]]=i; 
		}
		if(str == "Cancel") { k=read(); End[Real[k]]=i-1; }
		if(str == "Change") {
			k=read(); cin>>Z; ++tot2; 
			End[Real[k]]=i-1; 
			a[tot2] = a[Real[k]]; Real[k]=tot2; 
			a[tot2].z = Z; 
			Begin[Real[k]]=i; 
		}
	}
	for(i=1; i<=tot2; ++i) 
		if(Begin[i]) {
			Z = (dis[a[i].u] ^ dis[a[i].v] ^ a[i].z); 
			if(!End[i]) End[i]=q; 
			Seg.add(1, 1, q, Begin[i], End[i], Z); 
		}
	Seg.que(1, 1, q, fo); 
	return 0;
}