P3224-[HNOI2012]永无乡
题目:
题目描述:
永无乡包含 $n$ 座岛，编号从 $1$ 到 $n$ ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 $n$ 座岛排名，名次用 $1$ 到 $n$ 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 $a$ 出发经过若干座（含 $0$ 座）桥可以 到达岛 $b$ ，则称岛 $a$ 和岛 $b$ 是连通的。
现在有两种操作：
B x y 表示在岛 $x$ 与岛 $y$ 之间修建一座新桥。
Q x k 表示询问当前与岛 $x$ 连通的所有岛中第 $k$ 重要的是哪座岛，即所有与岛 $x$ 连通的岛中重要度排名第 $k$ 小的岛是哪座，请你输出那个岛的编号。
输入格式:
第一行是用空格隔开的两个整数，分别表示岛的个数 $n$ 以及一开始存在的桥数 $m$。
第二行有 $n$ 个整数，第 $i$ 个整数表示编号为 $i$ 的岛屿的排名 $p_i$。
接下来 $m$ 行，每行两个整数 $u, v$，表示一开始存在一座连接编号为 $u$ 的岛屿和编号为 $v$ 的岛屿的桥。
接下来一行有一个整数，表示操作个数 $q$。
接下来 $q$ 行，每行描述一个操作。每行首先有一个字符 $op$，表示操作类型，然后有两个整数 $x, y$。
- 若 $op$ 为
Q，则表示询问所有与岛 $x$ 连通的岛中重要度排名第 $y$ 小的岛是哪座，请你输出那个岛的编号。 - 若 $op$ 为
B，则表示在岛 $x$ 与岛 $y$ 之间修建一座新桥。
输出格式:
对于每个询问操作都要依次输出一行一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出 $-1$ 。
样例:
样例输入1:
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
|
样例输出1:
思路:
实现:
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
| // Problem: P3224 [HNOI2012]永无乡
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3224
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//把这两个东西背下来
int Read()
{
int x = 0;
char c = getchar();
while (!isdigit(c))
c = getchar();
while (isdigit(c))
{
x = x * 10 + (c ^ 48);
c = getchar();
}
return x;
}
using namespace __gnu_pbds;
//把这个命名空间背下来
int imp[100005], fa[100005];
//重要程度，并查集
void init_set(int n)
{
for (int i = 1; i <= n; ++i)
fa[i] = i;
}
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void uni_set(int x, int y)
{
x = find(x), y = find(y);
fa[x] = y;
}
typedef tree<int, int, std::greater<int>, rb_tree_tag,
tree_order_statistics_node_update>
Tree;
Tree block[100005];
//每个点一棵红黑树，资瓷查询第k大
void init_tree(int n)
{
for (int i = 1; i <= n; ++i)
block[find(i)].insert(std::pair<int, int>(imp[i], i));
} //以重要度为关键字
void uni_tree(int x, int y)
{ //启发式合并
x = fa[x], y = fa[y];
if (x == y) //如果已在同一联通块中，直接返回
return;
int size_x = block[x].size(), size_y = block[y].size();
if (size_x > size_y)
std::swap(x, y); //x更小
Tree::point_iterator it = block[x].begin();
for (; it != block[x].end(); ++it)
{
block[y].insert(std::pair<int, int>(it->first, it->second));
// block[x].erase(it);
}
uni_set(x, y);
}
int main()
{
int n = Read(), m = Read();
init_set(n);
for (int i = 1; i <= n; ++i)
imp[i] = Read();
for (int i = 0; i < m; ++i)
uni_set(Read(), Read());
init_tree(n);
int q = Read();
char opt[5];
for (int i = 0; i < q; ++i)
{
scanf("%s", opt);
if (opt[0] == 'B')
uni_tree(Read(), Read());
else
{
int father = find(Read());
int k = Read();
if (k > block[father].size())
puts("-1");
else //注意，find_by_order找的是第k大，而且从0开始排
printf("%d\n", block[father].find_by_order(block[father].size() - k)->second);
}
}
return 0;
}
|