Description

OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

Input

Output

输出文件的行数为F命令的条数加一。对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。输出文件的最后一行包含一个整数，为离开公司的员工的总数。

Sample Input

Sample Output

HINT

?

I命令的条数不超过100000 A命令和S命令的总条数不超过100 F命令的条数不超过100000 每次工资调整的调整量不超过1000 新员工的工资不超过100000

?

Source

Splay

还是很简单的，就是多了一点技巧，就是延迟操作，因为每回每个都要加或减，没有必要加减都个更新一回树，存一个整形变量最后加就行了，就是减的时候有可能工资低于最低标准了之后会离开公司，所以要更新一下，如果这个点的key值小于min，那么他的左子树都小于min，所以root直接等于右子树，从右子树找，否则大的话，右子树都大，找他左子树，最后更新一下size。

我也是醉了，，最后输出离开公司的人数，，题目不是说读入的时候下小于min直接离开公司吗，，那不也叫离开公司吗，，那部分人居然不算。。

ac代码

?

/**************************************************************
    Problem: 1503
    User: kxh1995
    Language: C++
    Result: Accepted
    Time:640 ms
    Memory:16444 kb
****************************************************************/
 
#include
  
   
#include
   
     struct s { int key,left,right,size; }tree[1001000]; int top,root; void left_rot(int &x) { int y=tree[x].right; tree[x].right=tree[y].left; tree[y].left=x; tree[y].size=tree[x].size; tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1; x=y; } void right_rot(int &x) { int y=tree[x].left; tree[x].left=tree[y].right; tree[y].right=x; tree[y].size=tree[x].size; tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1; x=y; } void maintain(int &x,bool flag)//维护SBT状态 { if(flag==false) { if(tree[tree[tree[x].left].left].size>tree[tree[x].right].size) right_rot(x); else if(tree[tree[tree[x].left].right].size>tree[tree[x].right].size) { left_rot(tree[x].left); right_rot(x); } else return; } else { if(tree[tree[tree[x].right].right].size>tree[tree[x].left].size) left_rot(x); else if(tree[tree[tree[x].right].left].size>tree[tree[x].left].size) { right_rot(tree[x].right); left_rot(x); } else return; } maintain(tree[x].left,false); maintain(tree[x].right,true); maintain(x,true); maintain(x,false); } void insert(int &x,int key) { if(x==0) { x=++top; tree[x].left=0; tree[x].right=0; tree[x].size=1; tree[x].key=key; } else { tree[x].size++; if(key
    
     =tree[x].key); } } int remove(int &x,int key) { tree[x].size--; if(key>tree[x].key) remove(tree[x].right,key); else if(key
     
      
?