一. 题目

BZOJ传送门= ̄ω ̄=
LUOGU传送门= ̄ω ̄=
CODEVS传送门= ̄ω ̄=


[HNOI2012]永无乡

时间限制:10s 空间限制:128MB

题目描述

永无乡包含 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 个数,依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi,表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作,该部分的第一行是一个正整数 q, 表示一共有 q 个操作,接下来的 q 行依次描述每个操作,操作的格式如上所述,以大写字母 Q 或B 开始,后面跟两个不超过 n 的正整数,字母与数字以及两个数字之间用空格隔开。 对于 20%的数据 n≤1000,q≤1000

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

输出格式

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

样例输入

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
2
5
1
2

提示

没有写明提示

题目来源

没有写明来源


二. 题解

这题一看过去——我是并查集加启发式合并,你来A我呀!
。。。
然而蒟蒻不会打splay!也不会红黑树!也不会平衡树
因为我太弱了……
所以我打算用set或者map代替平衡树,然而——题目要求支持k大数查询……

set/map无能为力啊!

然而天无绝人之路——我们可以用pb_ds啊~

这里简单介绍一下pb_ds的树。

库文件:

使用命名空间:

建立一棵红黑树:

其中,第一个参数是键值类型(key),第二个是数据类型(data),第三个是比较函数(伪函数),第四个表示树的类型,如:

至于第五个参数,应该是定义树的更新方式,不是很明白,反正写这个就行了:

如果觉得背不下来,其实很简单——找到库文件,到文件中去搜关键字不就行了吗= ̄ω ̄=。
linux底下,pb_ds库在这个路径下:

/usr/include/c++/5.4.0/ext/pb_ds

在文件管理器中按CTRL+L可以输入路径,按ESC可以关闭输入路径。

windows下的我不讲——谁让你不用Linux?

然后用法和set/map几乎一模一样,insert啊find啊一应俱全。
关键的是pb_ds的具有找k大数的功能:

这个代码返回的是树tree中的第k大数的迭代器,是个pair的迭代器(除非你定义tree的第二个参数为null_type)。

为什么是$k-1$而不是$k$呢?原因在于这个函数其实返回的是树上有k-1个节点比他小的那个节点的迭代器,所以我们要找第k大,那么就有$k-1$个节点比他小,所以是$k-1$。


那么这道题就很简单了,并查集维护每个岛屿的父亲节点,父亲节点对应的树表示的集合就是那个联通块中的点所在集合,然后启发式合并。
启发式合并具体就是要合并两个集合,就把集合元素少的集合合并到集合元素多的集合中(枚举小集合中的每个元素,并且把它insert到大集合中),然后把并查集中拥有小集合的岛屿的祖先节点的父亲设为拥有大集合的岛屿,即可。

注意:在bzoj上随便就可以AC了,因为bzoj是算的总时间。而luogu上可能就会TLE……但还是可以解决的。比如启发式合并的时候完全不用清空没用的树(除非你怕空间不够),这样就可以省很多时间。但即使这样在LUOGU上还是A不了,一定要在函数前面inline一下……(我没有什么高深的卡常技巧……也许搞个循环展开也可以= ̄ω ̄=)

代码: