我这题竟然很早就做了……

求k小显然可以用平衡树。但是这个题还需要快速的合并平衡树，那就需要启发式合并了。

代码：

/**************************************************************
    Problem: 2733
    User: danihao123
    Language: C++
    Result: Accepted
    Time:3876 ms
    Memory:6680 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100005;
struct Node {
    Node *ch[2], *f;
    int v, siz, id;
    int d() {
        return this == f -> ch[1];
    }
    void sc(Node *c, int dir) {
        ch[dir] = c;
        c -> f = this;
    }
    void maintain() {
        siz = 1 + ch[0] -> siz + ch[1] -> siz;
    }
};
Node pool[maxn * 2]; int A[maxn];
Node *nil;
#define T(x) (pool + (x))
int n;
void init_pool() {
    nil = pool;
    nil -> v = 0;
    nil -> siz = 0;
    nil -> f = nil -> ch[0] = nil -> ch[1] = nil;
    nil -> id = 0;
    for(int i = 1; i <= n; i ++) {
        pool[i].v = A[i];
        pool[i].f = pool[i].ch[0] = pool[i].ch[1] = nil;
        pool[i].id = i;
        pool[i].maintain();
    }
}
 
void zig(Node *x) {
    int d = x -> d(); Node *p = x -> f;
    p -> sc(x -> ch[!d], d); p -> maintain();
    if(p -> f == nil) {
        x -> f = nil;
    } else {
        p -> f -> sc(x, p -> d());
    }
    x -> sc(p, !d); x -> maintain();
}
void splay(Node *x) {
    while(x -> f != nil) {
        Node *y = x -> f;
        if(y -> f != nil) {
            if(x -> d() ^ y -> d()) {
                zig(x);
            } else {
                zig(y);
            }
        }
        zig(x);
    }
}
void naive_ins(Node *rt, Node *x) {
    int dir = x -> v > rt -> v;
    if(rt -> ch[dir] == nil) {
        rt -> sc(x, dir);
    } else {
        naive_ins(rt -> ch[dir], x);
    }
    rt -> maintain();
}
void insert(Node *rt, Node *x) {
    naive_ins(rt, x);
    splay(x);
}
Node *kth(Node *x, int k) {
    Node *lc = x -> ch[0], *rc = x -> ch[1];
    if(k <= lc -> siz) {
        return kth(lc, k);
    } else if(k == lc -> siz + 1) {
        splay(x);
        return x;
    } else {
        return kth(rc, k - lc -> siz - 1);
    }
}
 
int fa[maxn], rk[maxn];
int anc(int x) {
    if(fa[x] == x) {
        return x;
    } else {
        return (fa[x] = anc(fa[x]));
    }
}
void link_set(int x, int y) {
    fa[x] = y;
}
void union_set(int x, int y) {
    link_set(anc(x), anc(y));
}
bool is_same(int x, int y) {
    return anc(x) == anc(y);
}
Node *link_tree(Node *rt, Node *x) {
    Node *p = rt;
    if(x -> ch[0] != nil) {
        p = link_tree(p, x -> ch[0]);
    }
    if(x -> ch[1] != nil) {
        p = link_tree(p, x -> ch[1]);
    }
    x -> ch[0] = x -> ch[1] = x -> f = nil;
    x -> maintain();
    insert(p, x);
    return x;
}
void merge_tree(Node *x, Node *y) {
    if(!is_same(x - pool, y - pool)) {
        splay(x), splay(y);
        if(x -> siz > y -> siz) {
            link_tree(x, y);
        } else {
            link_tree(y, x);
        }
        union_set(x - pool, y - pool);
    }
}
 
int main() {
    int m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) {
        fa[i] = i;
        scanf("%d", &A[i]);
    }
    init_pool();
    for(int i = 1; i <= m; i ++) {
        int u, v;
        scanf("%d%d", &u, &v);
        merge_tree(T(u), T(v));
    }
    int q; scanf("%d", &q);
    while(q --) {
        char buf[3];
        scanf("%s", buf);
        if(buf[0] == 'B') {
            int x, y;
            scanf("%d%d", &x, &y);
            if(x == 0 || y == 0) continue;
            merge_tree(T(x), T(y));
        } else {
            int x, k;
            scanf("%d%d", &x, &k);
            if(x == 0) continue;
            splay(T(x));
            if(k <= T(x) -> siz) {
                printf("%d\n", kth(T(x), k) -> id);
            } else {
                puts("-1");
            }
        }
    }
    return 0;
}

• 相关文章
• 全局相关文章