A1678 [NOI2004] 郁闷的出纳员

// A1678 [NOI2004] 郁闷的出纳员 —— 全局偏移量 + 平衡树（FHQ Treap）
//
// 维护公司里所有员工的工资，支持：
//   I k：新员工，初始工资 k（低于工资下界 min 的直接不计入，也不算离职）；
//   A k：所有人的工资加 k；
//   S k：所有人的工资减 k，扣完低于 min 的人立刻离开；
//   F k：查询当前第 k 多的工资，人数不足则输出 -1。
// 最后输出累计离职人数。
//
// 关键技巧：用一个全局偏移量 delta 记录所有 A/S 的累计效果。
// 树里存的是「实际工资 − delta」，于是：
//   A/S 只改 delta，O(1)；插入/删除时用 k − delta 换算；
//   实际工资 = 树里的值 + delta。
//
// 树里需要三个操作：插入、按值分裂（把所有小于某值的元素整体摘掉）、
// 查第 k 大。用支持子树大小的 FHQ Treap 完成。

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

typedef long long ll;

struct Node {
    int l = 0, r = 0, sz = 0;
    ll key = 0;
    unsigned pri = 0;
};

vector<Node> tr(1); // 0 号为空节点
mt19937 rng(712367821);
int root = 0;

int newNode(ll key) {
    tr.push_back({0, 0, 1, key, rng()});
    return (int)tr.size() - 1;
}

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

// 按值分裂：a 里是 <= key 的，b 里是 > key 的
void split(int x, ll key, int &a, int &b) {
    if (!x) {
        a = b = 0;
        return;
    }
    if (tr[x].key <= key) {
        a = x;
        split(tr[x].r, key, tr[x].r, b);
        pushUp(a);
    } else {
        b = x;
        split(tr[x].l, key, a, tr[x].l);
        pushUp(b);
    }
}

// 合并：a 里所有值都 <= b 里所有值
int merge(int a, int b) {
    if (!a || !b) return a ? a : b;
    if (tr[a].pri < tr[b].pri) {
        tr[a].r = merge(tr[a].r, b);
        pushUp(a);
        return a;
    }
    tr[b].l = merge(a, tr[b].l);
    pushUp(b);
    return b;
}

int size() { return tr[root].sz; }

void insertVal(ll key) {
    int a, b;
    split(root, key, a, b);
    root = merge(merge(a, newNode(key)), b);
}

// 删除所有小于 key 的元素，返回被删个数
int eraseLess(ll key) {
    int a, b;
    split(root, key - 1, a, b);
    int removed = tr[a].sz;
    root = b;
    return removed;
}

// 第 k 大（k 从 1 起）
ll kthLargest(int k) {
    int x = root;
    while (x) {
        int rs = tr[tr[x].r].sz;
        if (k <= rs) {
            x = tr[x].r;
        } else if (k == rs + 1) {
            return tr[x].key;
        } else {
            k -= rs + 1;
            x = tr[x].l;
        }
    }
    return 0;
}

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

    int n;
    ll minSalary;
    cin >> n >> minSalary;

    ll delta = 0;    // 全局偏移量
    ll leavers = 0;  // 累计离职人数
    for (int i = 0; i < n; i++) {
        char op;
        ll k;
        cin >> op >> k;
        if (op == 'I') {
            if (k < minSalary) continue; // 初始工资低于下界，直接不计入
            insertVal(k - delta);
        } else if (op == 'A') {
            delta += k;
        } else if (op == 'S') {
            delta -= k;
            leavers += eraseLess(minSalary - delta); // 实际工资 < 下界的人离职
        } else if (op == 'F') {
            if (k < 1 || k > size()) {
                cout << -1 << '\n';
            } else {
                cout << kthLargest((int)k) + delta << '\n';
            }
        }
    }
    cout << leavers << '\n';
    return 0;
}