A1679 [ZJOI2006] 书架

#include <bits/stdc++.h>
using namespace std;

// 隐式 Treap：书柜从上到下的顺序 = 树的中序遍历。
// 每个节点记子树大小，用来回答「上面有几本书」和「第几本是谁」。
const int MAXN = 80000 + 5;

struct Node {
    int l = 0, r = 0, fa = 0;      // 左右儿子、父亲
    int sz = 0;                    // 子树大小
    int val = 0;                   // 书号
    unsigned long long pri = 0;    // 随机优先级
};

Node tr[MAXN];
int tot = 0;
int where[MAXN];                  // 书号 -> Treap 节点
int root = 0;

unsigned long long seed = 88172645463325252ULL;
unsigned long long rnd() {
    seed ^= seed << 13;
    seed ^= seed >> 7;
    seed ^= seed << 17;
    return seed;
}

int newNode(int val) {
    int x = ++tot;
    tr[x].l = tr[x].r = tr[x].fa = 0;
    tr[x].sz = 1;
    tr[x].val = val;
    tr[x].pri = rnd();
    return x;
}

void pull(int x) {
    tr[x].sz = tr[tr[x].l].sz + tr[tr[x].r].sz + 1;
    if (tr[x].l) tr[tr[x].l].fa = x;
    if (tr[x].r) tr[tr[x].r].fa = x;
}

// 把 a 接在 b 前面：a 里的书全部排在 b 上面
int merge(int a, int b) {
    if (!a) { if (b) tr[b].fa = 0; return b; }
    if (!b) { tr[a].fa = 0; return a; }
    if (tr[a].pri > tr[b].pri) {
        tr[a].r = merge(tr[a].r, b);
        pull(a);
        tr[a].fa = 0;
        return a;
    } else {
        tr[b].l = merge(a, tr[b].l);
        pull(b);
        tr[b].fa = 0;
        return b;
    }
}

// 把 x 按「前 k 本」切开：a 拿到前 k 本，b 拿到剩下的
void split(int x, int k, int *pa, int *pb) {
    if (!x) { *pa = *pb = 0; return; }
    if (tr[tr[x].l].sz >= k) {
        int a, b;
        split(tr[x].l, k, &a, &b);
        tr[x].l = b;
        pull(x);
        tr[x].fa = 0;
        *pa = a;
        *pb = x;
    } else {
        int a, b;
        split(tr[x].r, k - tr[tr[x].l].sz - 1, &a, &b);
        tr[x].r = a;
        pull(x);
        tr[x].fa = 0;
        *pa = x;
        *pb = b;
    }
}

// x 的排名（从 0 起），也就是它上面有几本书
int rankOf(int x) {
    int res = tr[tr[x].l].sz;
    while (tr[x].fa) {
        int p = tr[x].fa;
        if (tr[p].r == x) res += tr[tr[p].l].sz + 1;
        x = p;
    }
    return res;
}

// 从上往下第 k+1 本书（k 从 0 起）
int kth(int k) {
    int x = root;
    while (x) {
        int ls = tr[tr[x].l].sz;
        if (k < ls) x = tr[x].l;
        else if (k == ls) return tr[x].val;
        else { k -= ls + 1; x = tr[x].r; }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int p;
        cin >> p;
        int x = newNode(p);
        where[p] = x;
        root = merge(root, x);
    }

    while (m--) {
        string op;
        int s;
        cin >> op >> s;
        int x = where[s];
        if (op == "Top") {
            int r = rankOf(x);
            int a, b, mid, c;
            split(root, r, &a, &b);
            split(b, 1, &mid, &c);
            root = merge(merge(mid, a), c);
        } else if (op == "Bottom") {
            int r = rankOf(x);
            int a, b, mid, c;
            split(root, r, &a, &b);
            split(b, 1, &mid, &c);
            root = merge(merge(a, c), mid);
        } else if (op == "Insert") {
            int t;
            cin >> t;
            int r = rankOf(x);
            int a, b, mid, c, a1, a2;
            split(root, r, &a, &b);
            split(b, 1, &mid, &c);
            split(a, r + t, &a1, &a2);
            root = merge(merge(a1, mid), merge(a2, c));
        } else if (op == "Ask") {
            cout << rankOf(x) << "\n";
        } else { // Query
            cout << kth(s - 1) << "\n";
        }
    }
    return 0;
}