题目：
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 行每行是用空格隔开的两个正整数 ai 和 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
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
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
5
1
2
2
5
1
2
题解：
splay+启发式合并裸题
启发式合并就是把size小的树暴力拆分成一个一个节点加到大树里面
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=1e5+;
int key[N],father[N],size[N],root[N],ances[N],son[N][];
int get(int x)
{
return son[father[x]][]==x;
}
int find(int x)
{
if(ances[x]==x) return x;
else return find(ances[x]);
}
void update(int x)
{
if(x)
{
size[x]=;
if(son[x][]) size[x]+=size[son[x][]];
if(son[x][]) size[x]+=size[son[x][]];
}
}
int n,m,q;
char s[];
inline void rotate(int x)
{
int old=father[x],fold=father[old],which=get(x);
son[old][which]=son[x][which^];father[son[old][which]]=old;
father[old]=x;son[x][which^]=old;father[x]=fold;
if(fold)
{
if(son[fold][]==old) son[fold][]=x;
else son[fold][]=x;
}
update(old),update(x);
}
inline void splay(int x,int to)
{
for(int fa;fa=father[x];rotate(x))
{
if(father[fa])
{
if(get(x)==get(fa)) rotate(fa);
else rotate(x);
}
}
root[to]=x;
}
inline void insert(int sz,int x,int to)
{
if(!root[to])
{
root[to]=sz,father[sz]=son[sz][]=son[sz][]=;size[sz]=;return;
}
int now=root[to],fa=;
while(true)
{
fa=now;
now=son[now][x>key[now]];
if(!now)
{
father[sz]=fa;
son[sz][]=son[sz][]=;
size[sz]=;
son[fa][x>key[fa]]=sz;
update(sz);
update(fa);
splay(sz,to);
return;
}
}
}
inline void cut(int now,int to)
{
if(son[now][]) cut(son[now][],to);
if(son[now][]) cut(son[now][],to);
insert(now,key[now],to);
}
int query(int root,int k)
{
int now=root;
while(true)
{
if(son[now][]&&k<=size[son[now][]]) now=son[now][];
else
{
int temp=size[son[now][]]+;
if(temp==k) return now;
k-=temp;
now=son[now][];
}
}
}
int main()
{
// freopen("a.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%d",&key[i]);
ances[i]=root[i]=i;
father[i]=son[i][]=son[i][]=;
size[i]=;
}
for(int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
int fu=find(u);
int fv=find(v);
if(fu==fv) continue;
if(size[root[fu]]>size[root[fv]])
{
swap(u,v);
swap(fu,fv);
}
cut(root[fu],fv);
ances[fu]=fv;
}
scanf("%d",&q);
int u,v;
for(int i=;i<=q;i++)
{
scanf("%s",s);
if(s[]=='B')
{
scanf("%d%d",&u,&v);
int fu=find(u),fv=find(v);
if(fu==fv) continue;
else
{
if(size[root[fu]]>size[root[fv]])
swap(fu,fv),swap(u,v);
cut(root[fu],fv);
ances[fu]=fv;
}
}
else
{
scanf("%d%d",&u,&v);
int fu=find(u);
if(v>size[root[fu]]) printf("-1\n");
else
{
int ans=query(root[fu],v);
printf("%d\n",ans);
}
}
}
return ;
}