洛谷P3850 [TJOI2007] 书架 splay tree 模板题

题目链接：https://www.luogu.com.cn/problem/P3850

主要操作就是：插入 + 查询第 k 值。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1.1e5 + 5, maxb = 20;

struct Node {
    int s[2], p, sz;
    string name;
    Node() {}
    Node(string _name, int _p) { s[0] = s[1] = 0; p = _p; sz = 1; name = _name; }

} tr[maxn];
int root, idx;

void push_up(int x) {
    auto &u = tr[x], &l = tr[u.s[0]], &r = tr[u.s[1]];
    u.sz = l.sz + 1 + r.sz;
}

void f_s(int p, int u, int k) {
    tr[p].s[k] = u;
    tr[u].p = p;
}

void rot(int x) {
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    f_s(z, x, tr[z].s[1] == y);
    f_s(y, tr[x].s[k^1], k);
    f_s(x, y, k^1);
    push_up(y), push_up(x);
}

void splay(int x, int k) {
    while (tr[x].p != k) {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
            (tr[y].s[1]==x)^(tr[z].s[1]==y) ? rot(x) : rot(y);
        rot(x);
    }
    if (!k) root = x;
}

int n, m, q;
string book[202];
char ch[maxb];

int build(int l, int r, int p) {
    if (l > r) return 0;
    int mid = (l + r) / 2, x = mid;
    tr[x] = Node(book[mid], p);
    tr[x].s[0] = build(l, mid-1, x);
    tr[x].s[1] = build(mid+1, r, x);
    push_up(x);
    if (l == 1 && r == n) root = x;
    return x;
}

int get_k(int k) {
    int u = root;
    while (u) {
        if (tr[tr[u].s[0]].sz >= k) u = tr[u].s[0];
        else if (tr[tr[u].s[0]].sz + 1 == k) return u;
        else k -= tr[tr[u].s[0]].sz + 1, u = tr[u].s[1];
    }
    return -1;
}

void init() {
    tr[0].s[0] = tr[0].s[1] = tr[0].p = tr[0].sz = 0;
}

int cnt;
string ans[maxn];

void dfs(int u) {
    if (!u) return;
    dfs(tr[u].s[0]);
    ans[cnt++] = tr[u].name;
    dfs(tr[u].s[1]);
}

int main() {

    init();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        cin >> book[i];
    build(1, n, 0);
    root = (1 + n) / 2;
    idx = n;

    scanf("%d", &m);
    for (int i = 0; i < m; i++) {

        assert(tr[root].sz == n + i);

        int k;
        scanf("%s%d", ch, &k);
        string s = ch;
        if (k == 0) {
            int y = get_k(1);
            splay(y, 0);
            assert(!tr[y].s[0]);
            tr[++idx] = Node(s, y);
            tr[y].s[0] = idx;
            push_up(y);
        }
        else {
            int y = get_k(k);
            splay(y, 0);
            int z = tr[y].s[1];
            if (!z) {
                assert(!tr[y].s[1]);
                tr[++idx] = Node(s, y);
                tr[y].s[1] = idx;
                push_up(y);
            }
            else {
                while (tr[z].s[0]) z = tr[z].s[0];
                splay(z, y);
                assert(tr[y].s[1] == z && tr[y].s[1] == z);
                assert(!tr[z].s[0]);
                tr[++idx] = Node(s, z);
                tr[z].s[0] = idx;
                push_up(z), push_up(y);
                assert(y == root);
            }
        }
    }
    dfs(root);

    scanf("%d", &q);
    while (q--) {
        int x;
        scanf("%d", &x);
        printf("%s\n", ans[x].c_str());
    }

    return 0;
}