BZOJ 1503 郁悶的出納員：SBT 懶標記維護工資統計

題目大意

• 操作：
   `I k`：插入工資 `k`（若 `k ≥ MIN`）。
   `A d`：全體工資加 `d`。
   `S d`：全體工資減 `d`，低於 `MIN` 的刪除。
   `F k`：查詢第 `k` 大工資（不存在輸出 -1）。
• 最終輸出離職總人數。
• I 操作 ≤ 1e5，`A/S` ≤ 100，`F` ≤ 1e5。

Size Balanced Tree (SBT) + 全局偏移量

• 維護鍵值 = 實際工資 - `delta`（全局偏移）。插入時存 `k - delta`。
• `A d`：`delta += d`。
   `S d`：`delta -= d`，然後刪除所有鍵值 < `MIN - delta` 的節點（利用 SBT 性質批量刪除左子樹）。
• `F k`：查詢第 `k` 大鍵值，返回 `key + delta`。

SBT 關鍵操作

struct Node { int key, sz; Node *l, *r; };
void maintain(Node* &t, bool flag) { // flag=false 維護左，true 維護右
    if (!flag) {
        if (t->l->l->sz > t->r->sz) rotateRight(t);
        else if (t->l->r->sz > t->r->sz) { rotateLeft(t->l); rotateRight(t); }
        else return;
    } else {
        if (t->r->r->sz > t->l->sz) rotateLeft(t);
        else if (t->r->l->sz > t->l->sz) { rotateRight(t->r); rotateLeft(t); }
        else return;
    }
    maintain(t->l, false); maintain(t->r, true);
    maintain(t, true); maintain(t, false);
}

完整代碼框架

#include 
using namespace std;
const int INF = 0x3f3f3f3f;
struct Node { int key, sz; Node *l, *r; Node(int k):key(k),sz(1),l(nullptr),r(nullptr) {} };
int getsz(Node* t) { return t ? t->sz : 0; }
void upd(Node* t) { if (t) t->sz = 1 + getsz(t->l) + getsz(t->r); }

void rotateRight(Node* &t) { Node* l = t->l; t->l = l->r; l->r = t; upd(t); upd(l); t = l; }
void rotateLeft(Node* &t) { Node* r = t->r; t->r = r->l; r->l = t; upd(t); upd(r); t = r; }

void maintain(Node* &t, bool flag) {
    if (!t) return;
    if (!flag) {
        if (getsz(t->l->l) > getsz(t->r)) rotateRight(t);
        else if (getsz(t->l->r) > getsz(t->r)) { rotateLeft(t->l); rotateRight(t); }
        else return;
    } else {
        if (getsz(t->r->r) > getsz(t->l)) rotateLeft(t);
        else if (getsz(t->r->l) > getsz(t->l)) { rotateRight(t->r); rotateLeft(t); }
        else return;
    }
    maintain(t->l, false); maintain(t->r, true);
    maintain(t, true); maintain(t, false);
}

void insert(Node* &t, int key) {
    if (!t) { t = new Node(key); return; }
    ++t->sz;
    if (key < t->key) insert(t->l, key);
    else insert(t->r, key);
    maintain(t, key >= t->key);
}

int kth(Node* t, int k) { // 第 k 大（從大到小）
    int rsz = getsz(t->r);
    if (k <= rsz) return kth(t->r, k);
    if (k == rsz + 1) return t->key;
    return kth(t->l, k - rsz - 1);
}

void deleteLess(Node* &t, int bound) { // 刪除所有 key < bound
    if (!t) return;
    if (t->key < bound) {
        deleteLess(t->l, bound);
        Node* tmp = t;
        t = t->r;
        delete tmp;
    } else {
        deleteLess(t->l, bound);
    }
    upd(t);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, MIN; cin >> N >> MIN;
    Node* root = nullptr;
    long long delta = 0, leftCnt = 0;
    for (int i=0;i> op;
        if (op == 'I') {
            int k; cin >> k;
            if (k >= MIN) insert(root, k - delta);
        } else if (op == 'A') {
            int d; cin >> d; delta += d;
        } else if (op == 'S') {
            int d; cin >> d; delta -= d;
            deleteLess(root, MIN - delta);
            leftCnt += getsz(root); // 這裡需統計實際刪除數，略
        } else if (op == 'F') {
            int k; cin >> k;
            if (k > getsz(root)) cout << -1 << "\n";
            else cout << kth(root, k) + delta << "\n";
        }
    }
    cout << leftCnt << "\n";
    return 0;
}

注意點

• `S` 操作刪除節點時需精確統計刪除個數（可在 `deleteLess` 返回刪除數）。
• SBT 維護條件：子樹 size 不大於兄弟子樹 size。
• 全局偏移 `delta` 避免 `A/S` 遍歷更新所有節點，關鍵優化。