传送门：
CODEVS
BZOJ
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
Sample Output

-1
2
5
1
2

题解：
这个题目的解答很多，我因为智商余额不足，只会简单的主席树+并查集。
于是就直接用主席树来计算第K大，然后用并查集来更新根节点。
代码

/*
作者:WZH
题目:p1477 永无乡
*/
#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 100005,MAXX = 1800005;

int N,M,K,sz;
int fa[MAXN],V[MAXN],root[MAXN],id[MAXN];
int ls[MAXX],rs[MAXX],sum[MAXX];

inline int read(){
    int x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch)   {ch = getchar();}
    while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0' ;ch = getchar();}
    return x;
}

int Find_set(int x){ return fa[x] == x ? x : fa[x] = Find_set(fa[x]);} 

void insert(int &k,int l,int r,int v){
    if(!k) k = ++sz;
    if(l == r) {sum[k] = 1;return ;}
    int MID = (l + r) >> 1;
    if(v <= MID) insert(ls[k],l,MID,v);
    else insert(rs[k],MID+1,r,v);
    sum[k] = sum[ls[k]] + sum[rs[k]];
}

int query(int k,int l,int r,int rank){
    if(l == r) return l;
    int MID = (l + r) >> 1;
    if(sum[ls[k]] >= rank) return query(ls[k],l,MID,rank);
    else return query(rs[k],MID+1,r,rank - sum[ls[k]]);
}

inline void init(){
    N = read();M = read();
    
    for(int i = 1;i <= N;i++)
     V[i] = read(),fa[i] = i;
    
    int u,v;
    for(int i = 1;i <= M;i++){
        u = read();v = read();
        int fx = Find_set(u);
        int fy = Find_set(v);
        fa[fx] = fy;
    }
    
    for(int i = 1;i <= N;i++){
        insert(root[Find_set(i)],1,N,V[i]);
        id[V[i]] = i;
    }
}

int merge(int x,int y){
    if(!x) return y;
    if(!y) return x;
    ls[x] = merge(ls[x],ls[y]);
    rs[x] = merge(rs[x],rs[y]);
    sum[x] = sum[ls[x]] + sum[rs[x]];
    return x;
}

int main(){
    init();
    int x,k,TI;
    
    TI = read();char ch[2];
    
    for(int i = 1;i <= TI;i++)
    {
        scanf("%s",ch);
        x = read();k = read();
        if(ch[0] == 'Q') 
        {
            int p = Find_set(x);
            if(sum[root[p]] < k) printf("-1");
            else printf("%d\n",id[query(root[p],1,N,k)]);
        }    
        else {
            int p = Find_set(x),q = Find_set(k);
            if(p != q) fa[p] = q;    
            root[q] = merge(root[p],root[q]);
        }
    }
    return 0; 
}