BZOJ 4668 冷战

发表于 | 更新于

Link

感觉非常有意思啊

Solution

启发式合并的并查集树高O(logn)O(\log n)，那么直接在树上暴力LCA暴力最值就好啦。。。 之前还没见过这么玩的呢。。

Code

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
#include "lucida"
using std::fill;
using std::swap;
const int MAXN=500000+11;
int fa[MAXN],val[MAXN],sz[MAXN];
int Root(int x) {
	while(fa[x]) {
		x=fa[x];
	}
	return x;
}
void Union(int x,int y,int id) {
	int rx=Root(x),ry=Root(y);
	if(rx!=ry) {
		if(sz[rx]<sz[ry]) {
			swap(rx,ry);
		}
		fa[ry]=rx;val[ry]=id;
		sz[rx]+=sz[ry];
	}
}
int LCA(int x,int y) {
	static int us[MAXN],ut;
	++ut;
	do us[x]=ut;
	while ((x=fa[x]));
	while(us[y]!=ut) {
		y=fa[y];
	}
	return y;
}
int Query(int x,int y) {
	if(Root(x)!=Root(y)) {
		return 0;
	} else {
		int lca=LCA(x,y),res=0;
		for(;x!=lca;x=fa[x]) {
			chkmx(res,val[x]);
		}
		for(;y!=lca;y=fa[y]) {
			chkmx(res,val[y]);
		}
		return res;
	}
}
int main() {
	freopen("input","r",stdin);
	int n,m;is>>n>>m;
	fill(sz+1,sz+1+n,1);
	int last=0,ec=0;
	for(int i=1;i<=m;++i) {
		int opt,u,v;
		is>>opt>>u>>v;
		u^=last;v^=last;
		if(opt==0) {
			Union(u,v,++ec);
		} else {
			last=Query(u,v);
			os<<last<<'\n';
		}
	}
	return 0;
}