用平衡树维护就行了啊。
我用的是treap。
简单介绍一下treap：
treap类似普通的二叉搜索树，为了防止树退化成链，随机给每个节点赋一个值。
然后维护的时候，不仅需要节点值满足二叉搜索树的性质，还要保证看随机值的话，是一个小根堆。
利用旋转操作保证这个性质。
这里利用了取址来使p“作为son[fa[p]]”被修改，从而免去记录每个节点的父节点。
增减工资的操作，让人想到用懒惰标记。
然而每次都是全局修改，所以这里定义一个m起到了“大懒惰标记”的作用，注意要同时记录m0作为m的初值。
这道题题目描述有点问题。
如果加进来的时候初始工资就低于下限，这个人自然是不会被加进去的。
但他不会被算作是“气愤地离开公司”。
查询第k大值应该是平衡树的基本操作了吧，不再赘述。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<ctime> 5 using namespace std; 6 7 int n,m,m0,kick; 8 int s[100005][2],rd[100005],root,tot; 9 int v[100005],sz[100005],h[100005]; 10 11 void pushup(int p) 12 { 13 sz[p]=sz[s[p][0]]+sz[s[p][1]]+h[p]; 14 } 15 16 void zig(int &p) 17 { 18 int rs=s[p][1]; 19 s[p][1]=s[rs][0]; 20 s[rs][0]=p; 21 sz[rs]=sz[p]; 22 pushup(p); 23 p=rs; 24 } 25 26 void zag(int &p) 27 { 28 int ls=s[p][0]; 29 s[p][0]=s[ls][1]; 30 s[ls][1]=p; 31 sz[ls]=sz[p]; 32 pushup(p); 33 p=ls; 34 } 35 36 void in(int &p,int sal) 37 { 38 if(!p) 39 { 40 p=++tot; 41 v[p]=sal; 42 h[p]=sz[p]=1; 43 rd[p]=rand(); 44 return; 45 } 46 sz[p]++; 47 if(v[p]==sal)h[p]++; 48 else if(sal>v[p]) 49 { 50 in(s[p][1],sal); 51 if(rd[s[p][1]]<rd[p])zig(p); 52 }else 53 { 54 in(s[p][0],sal); 55 if(rd[s[p][0]]<rd[p])zag(p); 56 } 57 } 58 59 void del(int &p) 60 { 61 if(!p)return; 62 if(v[p]>=m) 63 { 64 del(s[p][0]); 65 pushup(p); 66 return; 67 } 68 kick+=sz[s[p][0]]+h[p]; 69 p=s[p][1]; 70 del(p); 71 pushup(p); 72 } 73 74 int qnum(int p,int rk) 75 { 76 if(rk<=sz[s[p][1]])return qnum(s[p][1],rk); 77 else if(rk<=sz[s[p][1]]+h[p])return v[p]; 78 else return qnum(s[p][0],rk-sz[s[p][1]]-h[p]); 79 } 80 81 int main() 82 { 83 srand(time(NULL)); 84 scanf("%d%d",&n,&m); 85 m0=m; 86 for(int i=1;i<=n;i++) 87 { 88 char op[5]; 89 int k; 90 scanf("%s",op+1); 91 scanf("%d",&k); 92 if(op[1]=='I')if(k>=m0)in(root,k+m-m0); 93 if(op[1]=='A')m-=k; 94 if(op[1]=='S')m+=k,del(root); 95 if(op[1]=='F') 96 { 97 if(sz[root]<k)printf("-1 "); 98 else printf("%d ",qnum(root,k)+m0-m); 99 } 100 } 101 printf("%d",kick); 102 return 0; 103 }