郁闷的出纳员
【问题描述】
OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。
工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。
老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。
好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？
【输入文件】
第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。
接下来的n行，每行表示一条命令。命令可以是以下四种之一：
名称
格式
作用
I命令
I_k
新建一个工资档案，初始工资为k。如果某员工的初始工资低于工资下界，他将立刻离开公司。
A命令
A_k
把每位员工的工资加上k
S命令
S_k
把每位员工的工资扣除k
F命令
F_k
查询第k多的工资
_（下划线）表示一个空格，I命令、A命令、S命令中的k是一个非负整数，F命令中的k是一个正整数。
在初始时，可以认为公司里一个员工也没有。
【输出文件】
输出文件的行数为F命令的条数加一。
对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。
输出文件的最后一行包含一个整数，为离开公司的员工的总数。
【样例输入】
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
【样例输出】
10
20
-1
2
【约定】
lI命令的条数不超过100000
lA命令和S命令的总条数不超过100
lF命令的条数不超过100000
l每次工资调整的调整量不超过1000
l新员工的工资不超过100000
【评分方法】
对于每个测试点，如果你输出文件的行数不正确，或者输出文件中含有非法字符，得分为0。
否则你的得分按如下方法计算：如果对于所有的F命令，你都输出了正确的答案，并且最后输出的离开公司的人数也是正确的，你将得到10分；如果你只对所有的F命令输出了正确答案，得6分；如果只有离开公司的人数是正确的，得4分；否则得0分。
【分析】
一段裸的splay，支持upper_bound，lowe_bound，然后和线段树一样Lazy_Tag一下（代码写得太丑QAQ）。
注：如果加入的员工由于工资小于最低工资立刻离开了公司，此人不计入被炒员工总数（于是本题为我的AC率做出了巨大的贡献）
也可以不Lazy_Tag，这题可以在外面开一个tag记录当前全体员工加了多少工资（tag<0就是减了多少工资）。一个员工的工资就是他原来的工资加上tag，新加入的员工的“原来的工资”就是他的工资减tag。
【代码】
#include <cstdio>using namespace std;int n,min_salary,delete_num;struct Node{Node *c[2];int v,s,tag;Node(){}Node(Node *p) {v=p->v;s=1;tag=0;c[0]=c[1]=NULL;}void Assign(int _v) {v=_v;}int Child_Size(int o) {return (c[o]==NULL)?0:c[o]->s;}void Update() {s=this->Child_Size(0)+this->Child_Size(1)+1;if (c[0]!=NULL) c[0]->tag+=tag;if (c[1]!=NULL) c[1]->tag+=tag;v+=tag;tag=0;}int cmp(Node *p) {return p->v<v;}int cmp(int k) {if (this->Child_Size(0)+1==k) return -1;return this->Child_Size(0)<k;}};struct Splay{Node *root,temp;int k;void Rotate(Node* &o,int d){o->Update();Node *p=o->c[d^1];p->Update();o->c[d^1]=p->c[d];p->c[d]=o;o->Update();p->Update();o=p;}void Splay_Node(Node* &o){if (o==NULL) {o=new Node(&temp);return;}o->Update();int d=o->cmp(&temp);Node *p=o->c[d];if (p==NULL) {Splay_Node(o->c[d]);Rotate(o,d^1);return;}p->Update();int d2=p->cmp(&temp);Splay_Node(p->c[d2]);if (d==d2) Rotate(o,d^1);else Rotate(o->c[d],d2^1);Rotate(o,d^1);}void Splay_Kth(Node* &o){o->Update();int d=o->cmp(k);if (d==-1) return;if (d) k-=o->Child_Size(0)+1;Node *p=o->c[d];p->Update();int d2=p->cmp(k);if (d2!=-1){if (d2) k-=p->Child_Size(0)+1;Splay_Kth(p->c[d2]);if (d==d2) Rotate(o,d^1);else Rotate(o->c[d],d2^1);}Rotate(o,d^1);}void _Delete(){Node *l=root->c[0],*r=root->c[1];delete root;root=NULL;if (l==NULL && r==NULL) return;else if (l!=NULL && r!=NULL) k=l->s,Splay_Kth(r),l->c[1]=r,root=l;else root=(r==NULL)?l:r;root->Update();}public:void Delete(){while (k=(root==NULL)?0:root->s){Splay_Kth(root);if (root->v>=min_salary) break;_Delete();delete_num++;}}void Insert(int _v) {temp.Assign(_v);Splay_Node(root);}void Add_Salary(int _v) {if (root!=NULL) root->tag+=_v;}void Salary_K(int _k){k=_k;if (root==NULL) printf("-1\n");else if (root->s<k) printf("-1\n");else Splay_Kth(root),printf("%d\n",(root->v<min_salary)?-1:root->v);}}T;void Work(){char ch;int x;while ((ch=getchar())==' ' || ch=='\n');scanf("%d",&x);if (ch=='I') if (x>=min_salary) T.Insert(x);if (ch=='A') T.Add_Salary(x);if (ch=='S') T.Add_Salary(-x),T.Delete();if (ch=='F') T.Salary_K(x);}int main(){scanf("%d%d",&n,&min_salary);for (int i=1;i<=n;i++) Work();printf("%d\n",delete_num);return 0;}
幸福就是重复。每天跟自己喜欢的人一起，通电话，
