3324 永无乡

compaq · 2024-12-29 10:51:25 · 个人记录

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n, m, q, f[N];
int root[N], tot;
int ls[N*20], rs[N*20], id[N*20], sum[N*20];
// id:节点编号， sum：重要度的出现次数之和 
// 时间空间复杂度为nlogn 
int find(int x){
    if(x == f[x])
        return x;
    return f[x] = find(f[x]);
}

void pushup(int p){
    sum[p] = sum[ls[p]] + sum[rs[p]];
}

int update(int u, int pl, int pr, int p, int i){
    if(!u) u = ++tot;
    //sum[u] ++; //如果sum[u]++写在这里，就可以不需要pushup操作。 
    if(pl == pr){
        id[u] = i;
        sum[u] ++;
        return u;
    }
    int mid = (pl + pr) / 2;
    if(p <= mid)
        ls[u] = update(ls[u], pl, mid, p, i);
    else
        rs[u] = update(rs[u], mid+1, pr, p, i);
    pushup(u);
    return u; 
}

int merge(int x, int y, int pl, int pr){
    if(!x || !y) return x + y;
    if(pl == pr){
        sum[x] += sum[y];
        return x;
    }
    int mid = (pl + pr) / 2;
    ls[x] = merge(ls[x], ls[y], pl, mid);
    rs[x] = merge(rs[x], rs[y], mid + 1, pr);
    pushup(x);
    return x;
}
int query(int u, int pl, int pr, int k){
    if(pl == pr) return id[u];
    int ans = 0;
    int mid = (pl + pr) / 2;
    if(k <= sum[ls[u]]) ans = query(ls[u], pl, mid, k);
    else ans = query(rs[u], mid+1, pr, k-sum[ls[u]]);
    return ans;
}

int main(){
    int x, y;
    scanf("%d%d",&n, &m);
    for(int i=1; i<=n; i++){
        f[i] = i;
        scanf("%d",&x);
        root[i] = update(root[i], 1, n, x, i); 
    }
    for(int i=1; i<=m; i++){
        scanf("%d%d",&x, &y);
        x = find(x);
        y = find(y);
        if(x == y) continue; 
        f[y] = x;
        root[x] = merge(root[x], root[y], 1, n);
    }
    scanf("%d",&q);
    while(q--){
        char ch[5];
        scanf("%s", ch);
        if(ch[0] == 'B'){
            scanf("%d%d",&x, &y);
            x = find(x);
            y = find(y);
            if(x == y) continue;
            f[y] = x;
            root[x] = merge(root[x], root[y], 1, n); 
        }
        else{
            scanf("%d%d",&x, &y);
            x = find(x);
            int ans = query(root[x], 1, n, y);
            ans = ans? ans:-1;
            printf("%d\n", ans); 
        }
    }
    return 0;
}