大致题意： 你是一个公司的出纳员，现在有(n)个操作，操作有4种：新来一个员工、增加全体员工工资、减少全体员工工资、查询第(k)多的工资。若一个员工的工资在某一时刻低于合同上的工资(m)，他会立刻离开公司。要你回答每一个询问并统计出离开公司的人数。
平衡树
比较显然，这是一道平衡树的题目。
至于用哪一种平衡树，我感觉这题用(Splay)比较方便吧！
这道题目的关键就在于，如何解决增加全体员工工资和减少全体员工工资。
其实，直接用一个变量(flag)来存储每个员工的工资变化情况即可。
每当增加全体员工工资，我们直接修改变量的值即可。
但是，如果减少全体员工工资，我们就要考虑是否有员工的工资低于(m)，此时就需要工资低于(m-flag)的员工从树上删去，那么，我们可以把树上(m-flag)的前驱找到，然后将其用(Splay)操作旋转直至根节点，将此次要删去的员工数给统计下来后，将根节点更新为根节点的右儿子即可。
还有一个要注意的细节就是，每当新增一个员工时，由于之前每次调整工资时他都不在，所以要先将其工资减去(flag)，然后再插入(Splay)中。
代码
#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define LL long long
#define swap(x,y) (x^=y,y^=x,x^=y)
#define tc() (A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++)
#define pc(ch) (pp_<100000?pp[pp_++]=(ch):(fwrite(pp,1,100000,stdout),pp[(pp_=0)++]=(ch)))
#define N 100000
int pp_=0;char ff[100000],*A=ff,*B=ff,pp[100000];
using namespace std;
int n,m,rt,tot=0,ans=0,flag=0;
struct splay
{
int Son[2],Cnt,Size,Val,Father;
}node[N+5];
inline void read(int &x)
{
x=0;int f=1;char ch;
while(!isdigit(ch=tc())) f=ch^'-'?1:-1;
while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));
x*=f;
}
inline void write(int x)
{
if(x<0) pc('-'),x=-x;
if(x>9) write(x/10);
pc(x%10+'0');
}
inline int Which(int x)//判断当前节点是其父亲节点的左儿子还是右儿子
{
return node[node[x].Father].Son[1]==x;
}
inline void PushUp(int x)//更新当前节点信息
{
node[x].Size=node[node[x].Son[0]].Size+node[node[x].Son[1]].Size+node[x].Cnt;
}
inline void Rotate(int x,int &k)//将当前节点上旋
{
int fa=node[x].Father,grandpa=node[fa].Father,d=Which(x);
if(fa^k) node[grandpa].Son[Which(fa)]=x;
else k=x;
node[x].Father=grandpa,node[fa].Son[d]=node[x].Son[d^1],node[node[x].Son[d^1]].Father=fa,node[x].Son[d^1]=fa,node[fa].Father=x,PushUp(fa),PushUp(x);
}
inline void Splay(int x,int &k)//将x节点旋转至指定位置k
{
for(int fa=node[x].Father;x^k;fa=node[x].Father)//只要x还没到目标位置就一直Rotate
{
if(fa^k) Rotate(Which(fa)^Which(x)?x:fa,k);
Rotate(x,k);
}
}
inline void Insert(int &x,int val,int fa)//插入一个值为val的数
{
if(!x) {node[x=++tot].Val=val,node[x].Cnt=node[x].Size=1,node[x].Father=fa,node[x].Son[0]=node[x].Son[1]=0,Splay(x,rt);return;}
if(node[x].Val==val) {++node[x].Cnt,Splay(x,rt);return;}
if(node[x].Val>val) Insert(node[x].Son[0],val,x);
else Insert(node[x].Son[1],val,x);
}
inline int get_val(int rk)//求出排名为rk的数的值
{
int x=rt;
while(x)
{
if(node[node[x].Son[0]].Size>=rk) x=node[x].Son[0];
else if(node[node[x].Son[0]].Size+node[x].Cnt>=rk) {Splay(x,rt);return node[x].Val;}
else rk-=node[node[x].Son[0]].Size+node[x].Cnt,x=node[x].Son[1];
}
}
inline int get_pre(int val)//求出val的前驱的节点编号
{
int x=rt,pre=0;
while(x)
{
if(node[x].Val<val) pre=x,x=node[x].Son[1];
else x=node[x].Son[0];
}
return pre;
}
inline void Delete(int val)//删除小于val的数
{
int k=get_pre(val);//k记录val的前驱
if(k) Splay(k,rt),ans+=node[node[rt].Son[0]].Size+node[rt].Cnt,rt=node[rt].Son[1],PushUp(rt);//将k旋转至根节点，然后更新ans，删除这些节点
}
int main()
{
register int i;
for(read(n),read(m),i=1;i<=n;++i)
{
char op;int x;while(!isalpha(op=tc()));read(x);
switch(op)
{
case 'I':if(x>=m) Insert(rt,x-flag,0);break;//增加一个新的员工
case 'A':flag+=x;break;//增加全体员工的工资
case 'S':Delete(m-(flag-=x));break;//减少全体员工的工资，删去工资少于m的员工
case 'F':if(node[rt].Size<x) pc('-'),pc('1');else write(get_val(node[rt].Size-x+1)+flag);pc('
');break;//查询元素，由于询问的是从大到小的排名，所以要求的从小到大的排名就是rt的size减去询问的排名然后再加1
}
}
return write(ans),fwrite(pp,1,pp_,stdout),0;//最后输出答案
}