本文共 2110 字，大约阅读时间需要 7 分钟。

题目大意:

每个点有一个权值.并查集.在集合合并的过程中查询集合第k大.

题目思路:

并查集,每个点开个线段树.然后在并查集集合合并的过程中同时线段树合并即可.

AC代码:

#include
   
    using namespace std;#define mid ((l + r) >> 1)const int maxn = 1e5 + 5;int sum[maxn << 5] , ls[maxn << 5] , rs[maxn << 5] , rt[maxn] , tot;void pushup (int t){
       int tl = ls[t] , tr = rs[t];    sum[t] = sum[tl] + sum[tr];}int add (int l , int r , int t , int p , int c){
       int now = ++tot;    ls[now] = ls[t];    rs[now] = rs[t];    if (l == r) {
           sum[now] += c;        return now;    }    if (p <= mid) ls[now] = add(l , mid , ls[now] , p , c);    else rs[now] = add(mid + 1 , r , rs[now] , p , c);    pushup(now);    return now;}int ask (int l , int r , int t , int k){
       if (l == r) return l;    if (sum[ls[t]] >= k) return ask(l , mid , ls[t] , k);    return ask(mid + 1 , r , rs[t] , k - sum[ls[t]]);}int mer (int a , int b , int l , int r){
       if (!a) return b;    if (!b) return a;    if (l == r) {
           sum[a] += sum[b];        return a;    }    ls[a] = mer (ls[a] , ls[b] , l , mid);    rs[a] = mer (rs[a] , rs[b] , mid + 1 , r);    pushup(a);    return a;}int a[maxn] , f[maxn] , n , m , id[maxn];int getf (int x){
   return f[x]==x?x:f[x]=getf(f[x]);}int dsu_mer (int a , int b){
       int fa = getf(a) , fb = getf(b);    if (fa == fb) return false;    f[fb] = fa;    mer(rt[fa] , rt[fb] , 1 , n);    return true;}int main(){
       scanf("%d%d" , &n , &m);    for (int i = 1; i <= n ; i++){
           scanf("%d" , a + i);        id[a[i]] = i;        f[i] = i;        rt[i] = add(1 , n , rt[0] , a[i] , 1);    }    for (int i = 1; i <= m ; i++){
           int x , y; scanf("%d%d" , &x , &y);        dsu_mer (x , y);    }    char op[5];    int x , y , q;scanf("%d" , &q);    for (int i = 1; i <= q ; i++){
           scanf("%s" , op);        scanf("%d%d" , &x , &y);        if (op[0] == 'Q'){
               x = getf (x);            if (sum[rt[x]] < y){
                   printf("-1\n");            }else {
                   printf("%d\n" , id[ask(1 , n , rt[x] , y)]);            }        }else {
               dsu_mer (x , y);        }    }    return 0;}
   

转载地址：http://gadi.baihongyu.com/