「HNOI2012」永无乡

发表于 | | 浏览量： 次

平衡树真是神奇。

传送门

洛谷P3224

BZOJ2733

题解

对于每一个联通块，都可以用一棵Splay来维护。

对于合并操作，可以采用启发式合并的方法，将小Splay接到大的Splay上去，然后把小的Splay的每一个节点都旋转到根节点（其实就是相当于把小的Splay拆了之后一个个加入到大的Splay里）。

对于一个节点，由于每次都是由小树往大树里加，所以进行一次合并之后，树的大小至少变到原来小树的两倍。所以每一个节点最多被合并$\log n​$次。

所以时间复杂度为$\Theta(n\log^2n)$。

代码

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
int n,m,q;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline char GetCmd()
{
	char ch=getchar();
	while(ch!='B'&&ch!='Q') ch=getchar();
	return ch;
}
struct SplayTree
{
	int fa[maxn],cnt[maxn],que[maxn];
	inline int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
	struct Node{int siz,val,fa,son[2];}Tree[maxn];
	inline void PushUp(int rt){Tree[rt].siz=Tree[Tree[rt].son[0]].siz+Tree[Tree[rt].son[1]].siz+1;}
	inline int check(int x){return Tree[Tree[x].fa].son[1]==x?1:0;}
	inline void Rotate(int x)
	{
		int y=Tree[x].fa,z=Tree[y].fa,k=check(x),w=Tree[x].son[k^1];
		Tree[w].fa=y;
		Tree[y].son[k]=w;
		Tree[x].fa=z;
		Tree[z].son[check(y)]=x;
		Tree[y].fa=x;
		Tree[x].son[k^1]=y;
		PushUp(y);
		PushUp(x);
	}
	inline void Splay(int x)
	{
		while(Tree[x].fa)
		{
			int y=Tree[x].fa;
			if(Tree[y].fa)
			{
				if(check(x)==check(y)) Rotate(y);
				else Rotate(x);
			}
			Rotate(x);
		}
	}
	inline void Link(int a,int b)
	{
		if(getfa(a)==getfa(b)) return;
		if(cnt[getfa(a)]<cnt[getfa(b)]) swap(a,b);
		cnt[getfa(a)]+=cnt[getfa(b)];cnt[getfa(b)]=0;
		fa[fa[b]]=fa[a];
		Splay(b);Splay(a);
		int p=a,fa=0;
		while(p)
		{
			fa=p;
			p=Tree[p].son[Tree[b].val>Tree[p].val];
		}
		Tree[fa].son[Tree[b].val>Tree[fa].val]=b;
		Tree[b].fa=fa;
		int hed=0,til=1;
		que[1]=b;
		while(hed!=til)
		{
			hed++;
			if(Tree[que[hed]].son[0]) que[++til]=Tree[que[hed]].son[0];
			if(Tree[que[hed]].son[1]) que[++til]=Tree[que[hed]].son[1];
		}
		for(int i=1;i<=til;i++) Splay(que[i]);
	}
	inline int Kth(int x,int k)
	{
		Splay(x);
		int p=x;
		while(p)
		{
			if(Tree[Tree[p].son[0]].siz+1==k) return p;
			if(Tree[Tree[p].son[0]].siz+1>k) p=Tree[p].son[0];
			else{k-=Tree[Tree[p].son[0]].siz+1;p=Tree[p].son[1];}
		}
		return -1;
	}
}ST;
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		ST.fa[i]=i;ST.cnt[i]=1;
		ST.Tree[i].siz=1;
		ST.Tree[i].val=read();
	}
	for(int i=1;i<=m;i++)
	{
		int a=read(),b=read();
		ST.Link(a,b);
	}
	q=read();
	while(q--)
	{
		if(GetCmd()=='B')
		{
			int a=read(),b=read();
			ST.Link(a,b);
		}
		else
		{
			int x=read(),k=read();
			printf("%d\n",ST.Kth(x,k));
		}
	}
	return 0;
}