[HNOI2012]永无乡

发表于 | 阅读次数：

Description

有N个景点，编号从1到N。对所有景点，****给他们做了一个排名。

景点之间由道路连接。若一个景点a可以通过若干个节点到另一个景点b，则称这两个景点是连通的。

现在有两种操作：

B x y表示在景点x与景点y之间修建一条道路。

Q x k表示询问当前与景点x连通的所有景点中，排名第k的景点是哪个，请你输出那个景点的编号。

Input Format

第一行两个正整数N和M，分别表示景点的个数以及一开始存在的道路数。

接下来的一行有N个数，依次描述权王给景点1到景点N的排名（排名用1到N来表示）。

随后的M行每行两个正整数a和b，表示一开始就存在一条连接景点a与景点b的道路。

后面剩下的部分描述操作。

该部分的第一行是一个正整数q，表示一共有q个操作。

接下来的q行依次描述每个操作，操作的格式如上所述，以大写字母Q或B开始，后面跟两个不超过N的正整数。

Output Format

对于每个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

Hint

对于30%的数据$N \le 1000,q \le 1000$

对于60%的数据$N \le 10000,q≤10000$

对于100%的数据$N \le 100000,m \le n,q \le 300000$

题解

这道题暴力分非常高（所以我只打了暴力(因为正解不会)）

我们可以考虑对每个景点都维护一棵线段树，记录和他在同一联通块内的景点所有的$Rank$值。

这样我们要维护$N$棵线段树，空间显然无法承受。

那么我们就考虑动态加点。

对于加边操作来说，我们只需要进行合并线段树的操作就可以快速地合并两个不同联通块内的$Rank$值。

接下来就是板子了。这样就AC了。

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define Re register int

int tot,rt[3600005],ls[3600005],rs[3600005],Sum[3600005];
int N,M,Q,fa[100005],Ind[100005];

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	var=w?-x:x;
}
int GetF(int x) {return x==fa[x]?x:fa[x]=GetF(fa[x]);}
void Build(int &id,int l,int r,int x)
{
	if (!id) id=++tot; ++Sum[id];
	if (l==r) return; int mid=(l+r)>>1;
	if (x<=mid) Build(ls[id],l,mid,x);
	else Build(rs[id],mid+1,r,x);
}
int Query(int id,int l,int r,int x)
{
	if (l==r) return l; int mid=(l+r)>>1;
	if (x<=Sum[ls[id]]) return Query(ls[id],l,mid,x);
	else return Query(rs[id],mid+1,r,x-Sum[ls[id]]);
}
int Merge(int x,int y)
{
	if (!x) return y; if (!y) return x;
	ls[x]=Merge(ls[x],ls[y]);
	rs[x]=Merge(rs[x],rs[y]);
	Sum[x]=Sum[ls[x]]+Sum[rs[x]];
	return x;
}
int main(int argc, char const *argv[])
{
	scanf("%d%d\n",&N,&M);
	for (Re i=1,Rank; i<=N; ++i)
	{
		read(Rank); fa[i]=Ind[Rank]=i; //Ind记录下对应的景区号。
		Build(rt[i],1,N,Rank);
	}
	for (Re i=1,u,v; i<=M; ++i)
	{
		scanf("%d%d",&u,&v); u=GetF(u),v=GetF(v);
		if (u!=v) {rt[u]=Merge(rt[u],rt[v]); fa[v]=u;} //注意这里是将v并向u
	}
	scanf("%d\n",&Q);
	while (Q--)
	{ char opt; int x,k;
		scanf("%c%d%d\n",&opt,&x,&k);
		if (opt=='B')
		{
			x=GetF(x),k=GetF(k);
			if (x!=k) {rt[x]=Merge(rt[x],rt[k]); fa[k]=x;} //注意这里是将k并向x
		} else printf("%d\n",Sum[rt[GetF(x)]]<k?-1:Ind[Query(rt[GetF(x)],1,N,k)]);
	} return 0;
}