一. 题目

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 的树。

库文件：

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

使用命名空间：

using namespace __gnu_pbds;

建立一棵红黑树：

tree<int,int,less<int>,rb_tree_tag,tree_order_statistics_node_update>

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

splay_tree_tag;
rb_tree_tag;

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

tree_order_statistics_node_update

如果觉得背不下来，其实很简单——找到库文件，到文件中去搜关键字不就行了吗=￣ω￣=。
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.find_by_order(k-1)；

这个代码返回的是树 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 一下……（我没有什么高深的卡常技巧……也许搞个循环展开也可以=￣ω￣=）

代码：

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,int,less<int>,rb_tree_tag,tree_order_statistics_node_update> rbt;
template<typename tp>inline void read(tp & dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
rbt rbst[100005];
int n,m,q,root[100005],f[100005],ans;
inline int findf(int a){return f[a]==a?a:f[a]=findf(f[a]);}
inline void merge(int a,int b)
{
    a=findf(a),b=findf(b);
    if(rbst[root[a]].size()>rbst[root[b]].size())swap(root[a],root[b]);
    for(rbt::iterator i=rbst[root[a]].begin();i!=rbst[root[a]].end();i++)
        rbst[root[b]].insert(*i);
    f[a]=b;
}
int main()
{
    read(n),read(m);
    for(int i=1,j;i<=n;i++)
        read(j),f[i]=root[i]=i,rbst[i].insert(make_pair(j,i));
    for(int i=1,u,v;i<=m;i++)read(u),read(v),merge(u,v);
    read(q);
    for(int i=1,a,b;i<=q;i++)
    {
        char c=getchar();
        while(!isalpha(c))c=getchar();
        read(a),read(b);
        if(c=='B')merge(a,b);
        else
        {
            a=findf(a);
            ans=rbst[root[a]].find_by_order(b-1)->second;
            printf("%d\n",ans?ans:-1);
        }
    }
    return 0;
}