洛谷P3224 永无乡 - 连通块合并查询第k小权值 并查集+线段树合并

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5+5;

int w[N], p[N], lc[N*20], rc[N*20], rt[N*20], id[N*20], tot=0, n, m;
vector<int> v[N];
int tre[N*20], ans[N];//节点信息

void Insert(int &i, int l, int r, int x, int Id){//建树
    if(r<l) return;
    i=++tot;//点
    if(l==r){
        id[i]=Id;
        tre[i]++; return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid) Insert(lc[i], l, mid, x, Id);
    if(x>mid) Insert(rc[i], mid+1, r, x, Id);
    tre[i]=tre[lc[i]]+tre[rc[i]];//权值在区间[l, r]的元素个数
}

int Merge(int x, int y){//合并
    if(!x) return y;
    if(!y) return x;
    lc[x]=Merge(lc[x], lc[y]);
    rc[x]=Merge(rc[x], rc[y]);
    tre[x]=tre[lc[x]]+tre[rc[x]];//节点信息合并

    return x;
}

int query(int root, int l, int r, int x){//查询子树中权值<=x的节点个数
    if(!root) return -1;
    if(!x) return -1;
    if(l==r){
        if(tre[root]>=x){
            return id[root];
        }
        return -1;
    }
    int mid=(l+r)>>1;
    if(x>tre[lc[root]]) return query(rc[root], mid+1, r, x-tre[lc[root]]);
    else  return query(lc[root], l, mid, x);
}

int f[N];
int fd(int x){
    if(f[x]==x) return x;
    return f[x]=fd(f[x]);
}
int main(){

    int x, y, q;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%d", &w[i]);
        f[i]=i;
    }
    for(int i=1; i<=n; i++){
        Insert(rt[i], 1, n, w[i], i);
    }
    for(int i=1; i<=m; i++){
        scanf("%d%d", &x, &y);
        x=fd(x), y=fd(y); f[y]=x;
        rt[x]=Merge(rt[x], rt[y]);

    }
    scanf("%d", &q);
    while(q--){
        char op[5];
        scanf("%s%d%d", op, &x, &y);
        x=fd(x);
        if(op[0]=='B'){
            y=fd(y);
            if(x==y) continue;
            f[y]=x;
            rt[x]=Merge(rt[x], rt[y]);
            //cout<<rt[x]<<" : "<<tre[rt[x]]<<endl;
        }
        else{
            printf("%d\n", query(rt[x], 1, n, y));
        }
    }

    return 0;

}