题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1503
思路：很裸的一道数据结构，直接套BST，对于工资变动量的处理方法：用一个类似前缀和的方法，f(x)表示第x次工资调整后的工资变化量，然后在树节点中加一个域，表示该员工的在第几次工资调整后到达公司的，即可方便的计算出员工当前工资。
（注意：离开公司的人数不算刚到公司就立刻离开的人数）
代码（SBT）：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXA 101
int suff[MAXA];
int n,minc;
struct node {
node *left_child,*right_child;
int r,s,key;
};
node *bank,*roof;
int z=0;
int ans=0;
int left_ratote(node* &t){
node *k=(*t).right_child;
(*t).right_child=(*k).left_child;
(*t).s=(*(*t).left_child).s+(*(*t).right_child).s+1;
(*k).left_child=t;
(*k).s=(*t).s+(*(*k).right_child).s+1;
t=k;
return 0;
}
int right_ratote(node* &t){
node *k=(*t).left_child;
(*t).left_child=(*k).right_child;
(*t).s=(*(*t).left_child).s+(*(*t).right_child).s+1;
(*k).right_child=t;
(*k).s=(*t).s+(*(*k).left_child).s+1;
t=k;
return 0;
}
int maintain(node* &t){
if ((*(*(*t).left_child).left_child).s>(*(*t).right_child).s){
right_ratote(t);
maintain((*t).right_child);
maintain(t);
return 0;
}
if ((*(*(*t).left_child).right_child).s>(*(*t).right_child).s){
left_ratote((*t).left_child);
right_ratote(t);
maintain((*t).left_child);
maintain((*t).right_child);
maintain(t);
return 0;
}
if ((*(*(*t).right_child).right_child).s>(*(*t).left_child).s){
left_ratote(t);
maintain((*t).left_child);
maintain(t);
return 0;
}
if ((*(*(*t).right_child).left_child).s>(*(*t).left_child).s){
right_ratote((*t).right_child);
left_ratote(t);
maintain((*t).left_child);
maintain((*t).right_child);
maintain(t);
return 0;
}
return 0;
}
int INSERT(int x,node* &t){
if (t==bank){
t=new(node);
(*t).s=1;
(*t).key=x;
(*t).r=z;
(*t).left_child=(*t).right_child=bank;
return 0;
}
(*t).s++;
if (x<((*t).key+suff[z]-suff[(*t).r])){
INSERT(x,(*t).left_child);
} else INSERT(x,(*t).right_child);
maintain(t);
return 0;
}
int DELETE(node* &t){
if (t==bank){
return 0;
}
if ((*t).key+suff[z]-suff[(*t).r]<minc){
ans+=((*(*t).left_child).s+1);
t=(*t).right_child;
DELETE(t);
} else DELETE((*t).left_child);
if (t!=bank){
(*t).s=(*(*t).left_child).s+(*(*t).right_child).s+1;
maintain(t);
}
return 0;
}
int getrank(int x,node *t){
if (x-1==(*(*t).right_child).s){
return (*t).key+suff[z]-suff[(*t).r];
}
if (x-1<(*(*t).right_child).s){
return getrank(x,(*t).right_child);
}
return getrank(x-(*(*t).right_child).s-1,(*t).left_child);
}
int main(){
bank=new(node);
(*bank).s=0;
roof=(*bank).left_child=(*bank).right_child=bank;
scanf("%d%d",&n,&minc);
suff[z]=0;
while (n--){
char c[1];
int k;
scanf("%s%d",&c,&k);
switch (c[0]){
case 'I':
if (k<minc){
break;
}
INSERT(k,roof);
break;
case 'A':
z++;
suff[z]=suff[z-1]+k;
break;
case 'S':
z++;
suff[z]=suff[z-1]-k;
DELETE(roof);
break;
case 'F':
if (k>(*roof).s){
printf("-1\n");
break;
}
printf("%d\n",getrank(k,roof));
break;
}
}
printf("%d\n",ans);
return 0;
}
