题解 P3224 【[HNOI2012]永无乡】

zyh2333 · 2019-12-29 15:37:27 · 题解

题目中要求我们支持查询第k小值，所以容易想到权值线段树

然后又有合并操作，容易想到线段树合并

然后我们发现做的时候需要维护一下连通性，容易想到并查集

嗯，然后我们就能通过本题了！

还有几点要注意的地方：

1.并查集的合并和线段树的合并方向要一致 比如说并查集是f[b]=a,那么合并线段树也需要b向a合并的样子。

2.查询的时候，记得求出并查集的根再查询

可以说题目由此结束了，注意第k小的存在，这个才是解题的关键

#include <bits/stc++.h>

using namespace std;

const int N = 100010;
const int M = 3200010;
int n , m , q , cnt , rt[N] , f[N];
int ls[M] , rs[M] , id[M] , sum[M];
char ch[5];

inline int read(){
    int num = 0 , x = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            x = -x;
        c = getchar();
    }
    while(c <= '9' && c >= '0'){
        num = (num << 1) + (num << 3) + c - '0';
        c = getchar();
    }
    return num * x;
}

inline int getf(int x){
    return x == f[x] ? x : f[x] = getf(f[x]);
}

inline void update(int a){
    sum[a] = sum[ls[a]] + sum[rs[a]];
}

inline int add(int a , int x , int y , int pos , int idx){
    if(!a)
        a = ++cnt;
    if(x == y){
        id[a] = idx;
        sum[a]++;
        return a;
    }
    int mid = (x + y) >> 1;
    if(pos <= mid)
        ls[a] = add(ls[a] , x , mid , pos , idx);
    else    
        rs[a] = add(rs[a] , mid + 1 , y , pos , idx);
    update(a);
    return a;
}

inline int merge(int a , int b , int x , int y){
    if(!a)
        return b;
    if(!b)
        return a;
    if(x == y){ 
        if(id[b]){
            id[a] = id[b];
            sum[a] += sum[b];
        }
        return a;
    }
    int mid = (x + y) >> 1;
    ls[a] = merge(ls[a] , ls[b] , x , mid);
    rs[a] = merge(rs[a] , rs[b] , mid + 1 , y);
    update(a);
    return a;
}

inline int query(int a , int k , int x , int y){
    int ans;
    if(sum[a] < k || !a)
        return 0;
    if(x == y)
        return id[a];
    int mid = (x + y) >> 1;
    if(k <= sum[ls[a]])
        ans = query(ls[a] , k , x , mid);
    else
        ans = query(rs[a] , k - sum[ls[a]] , mid + 1 , y);
    return ans;
}

int main(){
    int x , y;
    n = read();
    m = read();
    for(register int i = 1 ; i <= n ; ++i){
        f[i] = i;
        x = read();
        rt[i] = add(rt[i] , 1 , n , x , i);
    }
    for(register int i = 1 ; i <= m ; ++i){
        x = read();
        y = read();
        x = getf(x);
        y = getf(y);
        f[y] = x;
        rt[x] = merge(rt[x] , rt[y] , 1 , n);
    }      
    q = read();
    while(q--){
        scanf("%s" , ch);
        if(ch[0] == 'B'){
            x = read();
            y = read();
            x = getf(x);
            y = getf(y);
            if(x == y)
                continue;
            f[y] = x;
            rt[x] = merge(rt[x] , rt[y] , 1 , n);
        }
        else{
            x = read();
            y = read();
            x = getf(x);
            int ans = query(rt[x] , y , 1 , n);
            if(!ans)
                printf("-1\n");
            else
                printf("%d\n",ans);
        }
    }
    return 0;
}