郁闷的出纳员

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 3245 字
支持：I招新员工、A全员加k、S全员减k、F
一本通
练习
正文

/*
原题：T1567 「一本通 4.6 练习 2」郁闷的出纳员（NOI2004）
题意：支持：I 招新员工(初始工资 k)、A 全员加 k、S 全员减 k、F 查询第 k 多的工资。
低于下界 min 的员工立即离职（招入时低于下界的不计入离职总数）。
思路：Treap 维护相对工资，用全局偏移 delta 记录全员加减。插入存 k-delta；
A/S 改 delta，S 后把“相对值 < min-delta”的全部删除（即实际低于 min）。
第 k 多 = 升序第 (size-k+1) 小，再 +delta。
复杂度：时间 O(n log n)，空间 O(n)。
易错点：I 时若 k<min 直接离开且不计入总数；S 后要删除相对值低于 min-delta 者并计数；
F 当 k>当前人数输出 -1；最终多输出一行总离职人数。split/merge 用下标返回避免悬垂引用。
*/
#include <bits/stdc++.h>
using namespace std;
struct Treap {
    struct Node {
        int l, r, pri, cnt, sz;
        long long key;
    };
    vector<Node> t;
    int root;
    Treap(){
        t.push_back({0, 0, 0, 0, 0, 0});
        root = 0;
    }
    int rnd(){
        return rand();
    }
    int newNode(long long key){
        t.push_back({0, 0, rnd(), 1, 1, key});
        return (int)t.size() - 1;
    }
    void upd(int x){
        if(x) t[x].sz = t[t[x].l].sz + t[t[x].r].sz + t[x].cnt;
    }
    pair<int, int> split(int x, long long key){
        if(!x) return {0, 0};
        if(t[x].key < key){
            auto p = split(t[x].r, key);
            t[x].r = p.first;
            upd(x);
            return {x, p.second};
        }else{
            auto p = split(t[x].l, key);
            t[x].l = p.second;
            upd(x);
            return {p.first, x};
        }
    }
    int merge(int L, int R){
        if(!L || !R) return L | R;
        if(t[L].pri > t[R].pri){
            t[L].r = merge(t[L].r, R);
            upd(L);
            return L;
        }else{
            t[R].l = merge(L, t[R].l);
            upd(R);
            return R;
        }
    }
    void insert(long long key){
        auto p = split(root, key);
        int L = p.first, R = p.second;
        auto p2 = split(R, key + 1);
        int M = p2.first, R2 = p2.second;
        if(M){
            t[M].cnt++;
            t[M].sz++;
        }else{
            M = newNode(key);
        }
        root = merge(merge(L, M), R2);
    }
    int eraseBelow(long long key){
        auto p = split(root, key);
        int L = p.first, R = p.second;
        int rem = t[L].sz;
        root = R;
        return rem;
    }
    int kth(int k){
        int x = root;
        while(x){
            int ls = t[t[x].l].sz;
            if(k <= ls) x = t[x].l;
            else if(k <= ls + t[x].cnt) return (int)t[x].key;
            else {
                k -= ls + t[x].cnt;
                x = t[x].r;
            }
        }
        return -1;
    }
    int size(){
        return t[root].sz;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, minw;
    cin >> n >> minw;
    Treap tr;
    long long delta = 0;
    int left = 0;
    while(n--){
        char op;
        long long k;
        cin >> op >> k;
        if(op == 'I'){
            if(k < minw) continue;
            tr.insert(k - delta);
        } else if(op == 'A'){
            delta += k;
        } else if(op == 'S'){
            delta -= k;
            left += tr.eraseBelow(minw - delta);
        }else{
            if(k > tr.size()){
                cout << "-1\n";
            }else{
                long long key = tr.kth(tr.size() - k + 1);
                cout << key + delta << "\n";
            }
        }
    }
    cout << left << "\n";
    return 0;
}
郁闷的出纳员

正文

一本通·提高篇的其它内容
