题目描述

永无乡包含 nn 座岛，编号从 11 到 nn ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 nn 座岛排名，名次用 11 到 nn 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 aa 出发经过若干座（含 00 座）桥可以 到达岛 bb ，则称岛 aa 和岛 bb 是连通的。

现在有两种操作：

B x y 表示在岛 xx 与岛 yy 之间修建一座新桥。

Q x k 表示询问当前与岛 xx 连通的所有岛中第 kk 重要的是哪座岛，即所有与岛 xx 连通的岛中重要度排名第 kk 小的岛是哪座，请你输出那个岛的编号。

输入输出格式

输入格式：

 

第一行是用空格隔开的两个正整数 nn 和 mm ，分别表示岛的个数以及一开始存在的桥数。

接下来的一行是用空格隔开的 nn 个数，依次描述从岛 11 到岛 nn 的重要度排名。随后的 mm 行每行是用空格隔开的两个正整数 a_iai​ 和 b_ibi​ ，表示一开始就存在一座连接岛 a_iai​ 和岛 b_ibi​ 的桥。

后面剩下的部分描述操作，该部分的第一行是一个正整数 qq ，表示一共有 qq 个操作，接下来的 qq 行依次描述每个操作，操作的 格式如上所述，以大写字母 QQ 或 BB 开始，后面跟两个不超过 nn 的正整数，字母与数字以及两个数字之间用空格隔开。

 

输出格式：

 

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

对于 20% 的数据

 n \leq 1000, q \leq 1000n≤1000,q≤1000

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

n≤100000,m≤n,q≤300000

思路平衡树合并   把两个平衡树中小的那个拆开每一个加入到大的平衡树中

 

细节 本蒟蒻在这个地方出错了  2个平衡树用并差集合并后 其父节点既不是x也不是y也不是 find（x）也不是find（y） 是小的平衡树想大的平衡树里加的最后一个元素 那个元素是新的平衡树的 新的根节点 

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn  = 100000+7;int f[maxn],val[maxn];void init(){
    for(int i=0;i
         
          val[u]];}    if(ff)ch[ff][val[x]>val[ff]]=x;    fa[x]=ff;siz[x]=1;    ch[x][0]=ch[x][1]=0;    splay(x,0);}int temdata[maxn],cnt=0;void getall(int x){    if(ch[x][0])getall(ch[x][0]);    temdata[cnt++]=x;    if(ch[x][1])getall(ch[x][1]);}void merge(int x,int y){    if(find(x)==find(y))return;    x=find(x),y=find(y);    if(siz[x]
          
           =k)return find_k(ch[x][0],k);    return find_k(ch[x][1],k-siz[ch[x][0]]-1);}int main(){    init();    for(int i=1;i