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。
原来HN省选也有这么水的题233~
这道题这么显然，区间k小数，那么要么就是平衡树，要么就是权值线段树，而这两个东西在合并时都可以启发式合并。所谓的启发式就是每次把两棵树合并的时候，把节点数较少的那一颗给拆了，每个节点依次插入到另一颗树中去。这样由于每次一个节点重新插入时它所在的树大小都会翻倍，这样也就保证了每个节点最多被插入$\log n$次。于是就可以愉快的解决了。时间复杂度$O(n\log ^2 n)$。
UPD:听说这样子的线段树合并是$O(n\log n)$的，因为每个节点只会被访问到子树大小那么多次，因此复杂度为$O(n\log n)$。
我写的权值线段树，有点丑，凑合着看吧。 下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 100010
#define MAXN maxn*20 using namespace std;
typedef long long llg; int n,m,q,a[maxn],fa[maxn],siz[maxn],fr[maxn];
int rt[maxn],le[MAXN],ri[MAXN],sumv[MAXN],tt; int getint(){
int w=0;bool q=0;
char c=getchar();
while((c>'9'||c<'0')&&c!='-') c=getchar();
if(c=='-') c=getchar(),q=1;
while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?-w:w;
} int find(int x){return fa[fa[x]]==fa[x]?fa[x]:fa[x]=find(fa[x]);}
void insert(int u,int x){
int l=1,r=n,mid; fr[x]=u;
while(l!=r){
mid=(l+r)>>1; sumv[u]++;
if(x<=mid){
if(!le[u]) le[u]=++tt;
r=mid,u=le[u];
}
else{
if(!ri[u]) ri[u]=++tt;
l=mid+1,u=ri[u];
}
}
sumv[u]++;
} int merge(int u1,int u2){
if(!u1 || !u2) return u1+u2;
le[u1]=merge(le[u1],le[u2]);
ri[u1]=merge(ri[u1],ri[u2]);
sumv[u1]+=sumv[u2];
return u1;
} int work(int u,int k){
if(k>sumv[u]) return -1;
int l=1,r=n,mid;
while(l!=r){
mid=(l+r)>>1;
if(sumv[le[u]]>=k) u=le[u],r=mid;
else k-=sumv[le[u]],l=mid+1,u=ri[u];
}
return fr[l];
} int main(){
File("a");
n=getint(); m=getint(); tt=n;
for(int i=1;i<=n;i++) siz[i]=1,fa[i]=i,rt[i]=i,insert(rt[i],getint());
while(m--){
int x=getint(),y=getint();
x=find(x); y=find(y);
if(siz[x]>siz[y]) swap(x,y);
fa[x]=y; siz[y]+=siz[x];
rt[y]=merge(rt[y],rt[x]);
}
q=getint();
while(q--){
char c=getchar();
while(c!='Q' && c!='B') c=getchar();
int x=getint(),y=getint();
if(!x && !y) continue;
if(c=='B'){
x=find(x); y=find(y);
if(siz[x]>siz[y]) swap(x,y);
fa[x]=y; siz[y]+=siz[x];
rt[y]=merge(rt[y],rt[x]);
}
else printf("%d\n",work(rt[find(x)],y));
}
return 0;
}