[NOI 2004] 郁闷的出纳员

知识点

树状数组、离线离散化、全局偏移、顺序统计

解题思路

所有员工工资减去全局偏移量后保持不变。先读完命令，计算每次插入的归一化工资并离散化；回放时用树状数组保存计数。加减工资只改偏移，扣薪后删除低于下界的值；第k高转为第总数-k+1小，用树状数组查找。

正确性说明

归一化工资+偏移量始终等于实际工资，因此集体调整不必逐个改数。离散化只改变顺序编号，不改变工资比较；删除阈值以下的全部计数恰对应离职员工。树状数组前缀和给出排名，二进制定位可恢复第k个工资。初始未达标者不入树也不计离职，满足题意。

易错点

低于下界才离职，等于下界保留；忽略初始不达标者；允许0条命令；F的名次超过人数输出-1；偏移和归一化用64位。

复杂度

O(n log n)时间，O(n)空间；每次删除的一组员工均来自此前插入，删除总量有界。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
struct BIT{int n;vector<int>t;BIT(int n):n(n),t(n+1){}void add(int x,int v){for(;x<=n;x+=x&-x)t[x]+=v;}int kth(int k){int x=0;for(int step=1<<20;step;step>>=1)if(x+step<=n&&t[x+step]<k)k-=t[x+=step];return x+1;}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;long long low;cin>>n>>low;vector<pair<char,long long>>ops(n);vector<long long>coords;long long off=0;for(auto&[op,k]:ops){cin>>op>>k;if(op=='I'&&k>=low)coords.push_back(k-off);else if(op=='A')off+=k;else if(op=='S')off-=k;}sort(coords.begin(),coords.end());coords.erase(unique(coords.begin(),coords.end()),coords.end());BIT bit(coords.size());vector<int>freq(coords.size()+1);int total=0,left=0;off=0;for(auto[op,k]:ops){if(op=='I'){if(k<low)continue;int idx=lower_bound(coords.begin(),coords.end(),k-off)-coords.begin()+1;bit.add(idx,1);freq[idx]++;total++;}else if(op=='A')off+=k;else if(op=='S'){off-=k;while(total){int idx=bit.kth(1);if(coords[idx-1]+off>=low)break;int count=freq[idx];freq[idx]=0;bit.add(idx,-count);total-=count;left+=count;}}else{if(k>total)cout<<-1<<'\n';else cout<<coords[bit.kth(total-(int)k+1)-1]+off<<'\n';}}cout<<left<<'\n';}