HNOI2012 永无乡

发表于 | 分类于

[HNOI2012] 永无乡

Description

永无乡包含 $n$ 座岛，编号从$1 $到$ n$，每座岛都有自己的独一无二的重要度，按照重要度可 以将这$ n $座岛排名，名次用 $1 $到 $n $来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含$ 0 $座）桥可以到达岛$ b$，则称岛$ a $和岛$ b $是连 通的。

现在有两种操作：

  • B x y 表示在岛 x 与岛 y 之间修建一座新桥。
  • Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座，请你输出那个岛的编号。

Input

输入文件第一行是用空格隔开的两个正整数 $n $和 $m$，分别 表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的$ n $个数，依次描述从岛$ 1 $到岛$ n $的重要度排名。随后的 $m $行每行是用空格隔开的两个正整数 $a_i $和 $bi$，表示一开始就存 在一座连接岛$ ai $和岛$ bi $的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数$ q$， 表示一共有$ q $个操作，接下来的 $q$ 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过$ n $的正整数，字母与数字以及两个数字之间用空格隔开。

对于$ 20$%的数据$ n≤1000,q≤1000 $
对于$ 100$%的数据 $n≤100000,m≤n,q≤300000 $

Output

对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表 示所询问岛屿的编号。如果该岛屿不存在，则输出-1。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5 1           
4 3 2 5 1        
1 2           
7
Q 3 2           
Q 2 1 
B 2 3 
B 1 5 
Q 2 1 
Q 2 4 
Q 2 3

Sample Output

1
2
3
4
5
-1
2
5
1
2

题解

题目要求维护的是无向图的连通性和没个连通块的第$k$大。考虑最裸的维护无向图连通性和第$k$大的工具，就是并查集和平衡树。

考虑对于并查集中的每一个集合构建一颗平衡树，那么对于平衡树的合并，最差情况下，依次合并的话会退化为$O(n^2logn)$的复杂度。对于两个大小为$a\leq b$的平衡树，自然的想法是把$a$插入到$b$中，那么插入的个数是$O(a)$，是要小于$O(b)$的。事实上可以证明，这样插入均摊下来整体的复杂度是$O(nlogn)$的，那么这个算法就是正确的。通过重复利用结点，空间复杂度为$O(n)$。

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
133
134
135
136
137
138
139
140
141
#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+1e3+7;
int n,m,root[N],size[N],fa[N],F[N],w[N],pos[N],son[N][2],tot,key[N],q;
int find(int x)
{
	return F[x]==x?x:F[x]=find(F[x]);	
}
void pushup(int x)
{
	size[x]=1;
	if(son[x][0])
		size[x]+=size[son[x][0]];
	if(son[x][1])
		size[x]+=size[son[x][1]];
}
void rotate(int x)
{
	int y=fa[x],z=fa[y],t=(son[y][0]==x);
	if(z)
		son[z][son[z][1]==y]=x;
	fa[x]=z;
	son[y][!t]=son[x][t];
	fa[son[x][t]]=y;
	son[x][t]=y;
	fa[y]=x;
	pushup(y);
	pushup(x);
}
void splay(int x,int s)
{
	while(fa[x]!=s)
	{
		int y=fa[x],z=fa[y];
		if(z!=s)
		{
			if(son[y][0]==x^son[z][0]==y)
				rotate(x);
			else
				rotate(y);
		}
		rotate(x);
	}
	if(!s)
		root[find(x)]=x;
}
void insert(int &x,int s,int v,int p)
{
	if(!x)
	{
		x=p;
		size[x]=1;
		key[x]=v;
		fa[x]=s;
		splay(x,0);
		return;
	}
	insert(son[x][v>key[x]],x,v,p);
}
void merge(int x,int y)
{
	x=find(x),y=find(y);
	if(x==y)
		return;
	if(size[root[x]]>size[root[y]])
		swap(x,y);
	F[x]=y;
	queue<int>q;
	q.push(root[x]);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		if(son[u][0])
			q.push(son[u][0]);
		if(son[u][1])
			q.push(son[u][1]);
		insert(root[y],0,key[u],u);
	}
}
int kth(int x,int k)
{
	x=root[find(x)];
    while(k<=size[son[x][0]]||k>size[son[x][0]]+1)
    {
        if(k<=size[son[x][0]])
            x=son[x][0];
        else
            k-=size[son[x][0]]+1,x=son[x][1];
    }
    return x;
}
int main()
{
	freopen("bzoj_2733.in","r",stdin);
	freopen("bzoj_2733.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{	
		cin>>w[i],F[i]=i;
		pos[w[i]]=i;
		insert(root[i],0,w[i],i);
	}
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		merge(u,v);
	}
	cin>>q;
	while(q--)
	{
		char op;
		int x,y;
		cin>>op>>x>>y;
		if(op=='B')
			merge(x,y);
		else
		{
			if(size[root[find(x)]]<y)
				cout<<-1<<"\n";
			else
				cout<<kth(x,y)<<"\n";
		}
	}
}

而还有一种可以维护第$k$大的工具就是权值线段树。对于线段树的合并由于维护的是权值关系，每次新建节点的话，会导致空间复杂度退化为$O(n^2)$，而事实上最开始的空间复杂度，对于每个连通块都是一个单点，想要访问这个节点的信息只需要$O(logn)$个结点，所以采用我们每次只添加有用的点，类似于主席树后续版本的插入一样。对于需要的结点再分配空间。可以证明空间复杂度是$O(logn)$的，而每次对于每一层信息合并即可，一共有$O(logn)$层，复杂度也是$O(logn)$的。

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
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+1e3+7;
struct T{
	int ls,rs,sum;
}t[N*41];
int n,m,q,root[N],cnt,w[N],fa[N],pos[N];
int find(int x)
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
void update(int x)
{
	t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
}
void insert(int &x,int l,int r,int v)
{
	if(!x)
		x=++cnt;
	if(l==r)
	{
		t[x].sum=1;
		return;
	}
	int mid=(l+r)>>1;
	if(v<=mid)
		insert(t[x].ls,l,mid,v);
	else
		insert(t[x].rs,mid+1,r,v);
	update(x);
}
int kth(int x,int l,int r,int k)
{
	if(l==r)
		return l;
	int mid=(l+r)>>1;
	if(t[t[x].ls].sum>=k)
		return kth(t[x].ls,l,mid,k);
	else
		return kth(t[x].rs,mid+1,r,k-t[t[x].ls].sum);
}
int merge(int x,int y)
{
	if(!x)
		return y;
	if(!y)
		return x;
	t[x].ls=merge(t[x].ls,t[y].ls);
	t[x].rs=merge(t[x].rs,t[y].rs);
	update(x);
	return x;
}
int main()
{
	freopen("bzoj_2733.in","r",stdin);
	freopen("bzoj_2733.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>w[i],fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		fa[find(u)]=find(v);
	}
	for(int i=1;i<=n;i++)
	{
		insert(root[find(i)],1,n,w[i]);
		pos[w[i]]=i;
	}
	cin>>q;
	while(q--)
	{
		char op;
		int x,y;
		cin>>op>>x>>y;
		if(op=='B')
		{
			x=find(x),y=find(y);
			if(x==y)
				continue;
			fa[y]=x;
			root[x]=merge(root[x],root[y]);
		}
		else
		{
			x=find(x);
			if(t[root[x]].sum<y)
				cout<<-1<<"\n";
			else
				cout<<pos[kth(root[x],1,n,y)]<<"\n";
		}
	}
}