永无乡

洛谷-P3224-永无乡

实现

#include <iostream>
#define null 0
using namespace std;

const int N = 100010;
struct node {
    int ls, rs;
    int cnt;
    #define ls(x) t[x].ls
    #define rs(x) t[x].rs
    #define cnt(x) t[x].cnt
};
int tot, root[N];
node t[N * 4 * 20];
int n, m, q;
int h[N];
int f[N];

void update (int rt) {
    cnt(rt) = cnt(ls(rt)) + cnt(rs(rt));
}
int modify (int rt, int l, int r, int val, int delta) {
    if (rt == null) rt = ++ tot;
    if (l == r) {
        cnt(rt) += delta;
        return rt;
    }
    int mid = l + r >> 1;
    if (val <= mid)
        ls(rt) = modify(ls(rt), l, mid, val, delta);
    else
        rs(rt) = modify(rs(rt), mid + 1, r, val, delta);
    update(rt);
    return rt;
}
int query (int rt, int l, int r, int k) {
    if (l == r) return l;

    int mid = l + r >> 1;
    if (cnt(ls(rt)) >= k)
        return query(ls(rt), l, mid, k);
    else
        return query(rs(rt), mid + 1, r, k - cnt(ls(rt)));
}
int merge (int x, int y, int l, int r) {
    if (x == null || y == null) return x + y;
    if (l == r) {
        cnt(x) += cnt(y);
        return x;
    }
    int mid = l + r >> 1;
    ls(x) = merge(ls(x), ls(y), l, mid);
    rs(x) = merge(rs(x), rs(y), mid + 1, r);
    update(x);
    return x;
}
int find (int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}
void merge (int x, int y) {
    f[find(x)] = find(y);
}

int main () {
    scanf("%d%d", &n, &m);

    for (int i = 1, p; i <= n; ++ i) {
        scanf("%d", &p);
        h[p] = i; // 重要度 -> 编号
        root[i] = modify(root[i], 1, n, p, 1);
    }

    for (int i = 1; i <= n; ++ i) f[i] = i;
    for (int i = 1, u, v; i <= m; ++ i) {
        scanf("%d%d", &u, &v);
        root[find(u)] = merge(root[find(u)], root[find(v)], 1, n);
        merge(v, u);
    }

    scanf("%d", &q);
    while (q --) {
        char opt[5];
        scanf("%s", opt);
        if (opt[0] == 'B') {
            int x, y;
            scanf("%d%d", &x, &y);
            root[find(x)] = merge(root[find(x)], root[find(y)], 1, n);
            merge(y, x);
        } else {
            int x, k;
            scanf("%d%d", &x, &k);
            int rt = root[find(x)];
            printf("%d\n", cnt(rt) >= k ? h[query(rt, 1, n, k)] : -1);
        }
    }
    return 0;
}