出纳员
　【问题描述】　OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调整工资他还做其它什么事情。
工资的频繁调整很让员工反感，尤其是集团扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤的离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去。同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。
老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。
好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？
【输入文件】第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。接下来的n行，每行表示一条命令。命令可以是表2-1所示的四种命令之一。
表2-1
名　称    格式    作　用
I命令    I_k    新建一个工资档案，初始工资为k。如果某员工的初始工资低于工资下界，他将立刻离开公司
A命令    A_k    把每位员工的工资加上k
S命令    S_k    把每位员工的工资扣除k
F命令    F-k    查询第k多的工资
_（下划线）表示一个空格，Ｉ命令、Ａ命令、Ｓ命令中的k是一个非负整数，Ｆ命令中的k是一个正整数。在初始时，可以认为公司里一个员工也没有。
　【输出文件】输出文件的行数为Ｆ命令的条数加一。对于每条Ｆ命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1.输出文件的最后一行包含一个整数，为离开公司的员工的总数。
　【样例输入】
9　10
I  60
I  70
S  50
F  2
I  30
S  13
A  5
F  1
F  2

　【样例输出】
10
20
-1
2

　【约定】
　Ｉ命令的条数不超过100000。
　Ａ命令和Ｓ命令的总条数不超过100。
　Ｆ命令的条数不超过100000。
　每次工资调整的调整量不超过1000。
　新员工的工资不超过100000。
　【评分方法】　对于每个测试点，如果你输出文件的行数不正确，或者输出文件中含有非法字符，等分为0.否则你的得分按如下方法计算：
　　如果对于所有的Ｆ命令，你都输出了正确的答案，并且最后输出的离开公司的人数也是正确的，你将得到10分；如果你只对所有的Ｆ命令输出了正确答案，得6分；如果只有离开公司的人数是正确的，得4分；否则得0分。



算法分析：
1.数据结构的最佳选择是静态排序二叉树
　设计本题的用意是为了考察选手对基本数据结构理解的程序和应用的能力。这道试题初看似乎简单，如果把问题规模撇到一边的话，很容易联想到一种朴素的算法：即用一个数组存储所有员工的工资。遇到A命令或S命令时，将数组中所有元素加上或减去一个值；遇到F命令时对数组元素进行排序。显然，这个算法的时间复杂度为O(I+I*(A+S)+I*log2I*F)（用字母表示相应命令的条数）。但问题是，I命令数和F命令数的上限为100000,使得上述程序的运行时间远远超出可以承受的范围。因此必须另辟蹊径，寻求高效率的数据结构和算法。
试题要求设计一种能实现如下４种操作的数据结构。
⑴　向集合中插入一个数；
⑵　将集合中所有的数都加上一个值；
⑶　将集合中所有的数都减去一个值，并将所有低于min的数从集合中删除掉（min是事先给定的工资下限）；
⑷　查找集合中第k大的数。
这些操作包含了插入、删除、元素，以及查找第k大的数，哪种数据结构给为这些操作提供有力的支撑呢？
从典型的二叉树排序中可以得到启发，根据试题要求，设计了一种静态二叉排序树的数据结构，使得上述４种操作的时间复杂度都为O(log2(limit)),其中limit为集合中的元素数，亦为静态二叉排序树的顶点数。
静态二叉排序树是指具有下列性质的非空二叉树：
⑴　若根结点的左子树不空，则左子树的所有结点值均小于根结点值；
⑵　苦根结点的右子树不空，则右子树的所有结点值均不小于根结点值；
⑶　根结点的左右子树也分别为二叉排序树；
⑷　根结点的值为区间的中间点。
例如集合｛3,4,5,8,19,6｝,对应的静态二叉排序树如图所示。
显然，静态二叉排序树是一棵满二叉树。对这棵树进行中序遍历，即可得出集合元素的升序排列。把X映射中的点值填入到树中，使它有上面的构造。二叉树的顶点从上到下，从左到右编号，并令根结点的编号为1。即图××中对应的编号应如图××所示。
对于任何一个编号为i的结点，它的左儿子编号自然为i*2,右儿子编号为i*2+1.现在要把X的映射填入到数组t中去，t[1..n]应该保存相应位置上的点值。
设
const
  limitm=100;                                　　　{A命令和S命令数的上限}
  limitl=100000;　　　　　　　　　　　　　　　　　　　　　｛F命令数的上限｝
  limitaddvalue=1000;　　　　　　　　　　　　　　　　　｛每次调整量的上限｝
  limitvalue=100000;　　　　　　　　　　　　　　　　　　｛新员工工资的上限｝
  limittree=limitvalue*10;　　　　　　　　　　　　　｛静态排序二叉树的规模｝
  limitadd=limitaddvalue*limitm;　　　　　　　　　　　　｛工资调整量的上限｝
显然，员工工资的下限为-limitadd，上限为limitvalue+limitadd。下面，我们设法将工资区间［-limitadd,limitvalue+limitadd］的映射填入到静态排序二叉树t中去。设
type
  node=record　　　　　　　　　　　　　　　｛静态排序二叉树顶点的数据类型｝
       value,num,nodenum:longint;　｛工资，同一工资的人数，子树的顶点总数｝
       end;
var
  t:array[0..limittree] of node;　　　　　　　　　　　　　｛静态排序二叉树｝
procedure build_tree(now,l,r:longint);｛把工资区间［l,r］的映射填入到以 now顶点为根的静态排序二叉树中去｝
var
  m:longint;
begin
  m:=(l+r) div 2;　　　　｛计算工资区间[l,r]的中间位置，记为now顶点的工资｝
  t[now].value:=m;
  if l<m then build_tree(now*2,l,m-1);｛将左区间[l,m-1]的映射填入到以now*2顶点为根的左子树中去｝
  if m<r then build_tree(now*2+1,m+1,r);｛将右区间[m+1,r]的映射填入到以now*2+1顶点为根的dk 子树中去｝
end;{build_tree}

procedure init_tree; 　　　　　　　　　　　　　 {建立初始的静态排序二叉树}
begin
  fillchar(t,sizeof(t),0);　｛静态排序二叉树初始化为空｝
  build_tree(1,-limitadd,limitvalue+limitadd);　　　　　　　　｛把工资区间[-limitadd,limitvalue+limitadd]的映射填入到静态排序二叉树t中去｝
end;{init_tree}
以后，每往静态排序二叉树t中插入一个员工的初始工资x,便要计算以每个结点v为根的子树上结点的总数t[v].nodenum。计算过程如下：
procedure insert_tree(x:longint);         　｛将工资x插入静态排序二叉树t｝
var
  now:longint;　　　　　　　　　　　　　　　　　　　　　　　｛当前顶点序号｝
begin
  now:=1;　　　　　　　　　　　　｛从根出发，自上而下的搜索工资为x的顶点｝
  while t[now].value<>x do begin　　　　　　　｛若now顶点的工资≠x，则循环｝
    inc(t[now].nodenum);                   　｛以now为根的子树的顶点数+1｝
    if t[now].value>x then now:=now*2 　　｛若x在左子树方向，则计算左指针｝
    else now:=now*2+1;　　　　　　　　　　｛否则x在右子树方向，计算右指针｝
    end;{while}
  inc(t[now].nodenum);　                      ｛以now为根的子树的顶点数+1｝
    inc(t[now].num);        ｛由于now顶点的工资为x，因此同一工资的人数+1｝
end;{insert_tree}
由于员工工资的下限为-limitadd,上限为limitvalue+limitadd，因此静态排序二叉树规模的上限limit=limitvalue+2*limitadd≤300000。显然，插入操作的时间复杂度为O(log2(limit))。
2.通过设立调整变量delta改善算法
如果单纯的按题目要求对数据进行改动，则由于需要重建二叉树，使得每次处理A命令和S命令的时间复杂度为O(n*log2n)（n为I命令数的上限），处理所有A命令和S命令的时间复杂度就为O(2*m*nlog2n)(m为A命令或S命令数的上限)，这是无法承受的。
现在，从另外一个角度考虑问题：A命令和S命令的操作不改变集合内元素的大小关系，仅对目前集合内的元素与以后将要加进集合的新元素间的大小关系产生影响。这样就可以只改变新进元素的值而不改变已有元素的值。具体做法是设立一个变量delta，用于存储调整量。
设
n,min,k,delta,thrownum,i:longint;｛n为命令数，min为工资下限，delta为工资调整量，thrownum为离开公司的人数｝
 command:char;　　　　　　　　　　　　　　　　　　　　　　　　　　｛命令字｝
有了变量delta，便可以通过下述方法改进时间效率。
⑴　如果遇到将集合内所有元素加x的A命令，则不改变集合内元素的值而令delta=delta+x。
procedure add(x:longint);                  　｛将新增工资x加入调整量delta｝
  begin
    inc(delta,x);
  end;{add}
显然，处理A命令的时间复杂度为O(1)。
⑵　同理遇到将集合内所有元素减x的S命令，则令delta=delta-x，同时将静态排序二叉树t中所有小于min-delta的顶点删除掉。
procedure update_tree(k:longint);｛将目前工资低于下限的顶点从静态排序二叉树t中去除｝
begin
  if t[k].nodenum=0 then exit;　　｛若不存在以k顶点为根的子树，则退出过程｝
  if 2*k<limittree then update_tree(2*k);　　｛若左子树存在，则递归左子树｝
  if (t[k].value+1<min-delta) and (2*k+1<limittree)｛若右子树存在，且右子树可能存在低于工资下限的顶点，则递归右子树｝
     then update_tree(2*k+1);
  if t[k].value+delta<min｛若k顶点经调整后的工资低于下限，则持该工资的所有员工离开公司｝
     then begin inc(thrownum,t[k].num);t[k].num:=0;end;{then}
  t[k].nodenum:=t[2*k].nodenum+t[k].num+t[2*k+1].nodenum;｛重新计算以k顶点为根的子树的顶点总数｝
end;{update_tree}

procedure sub(x:longint);｛在调整量delta中减去扣除的工资x，并从静态排序二叉树中去除工资低于下限的顶点｝
begin
  dec(delta,x);　　　　　　　　　　　　　｛在调整量delta中减去扣除的工资x｝
  update_tree(1);　　　｛将目前工资低于下限的顶点从静态排序二叉树t中去除｝
end;{sub}
显然，处理S命令的时间复杂度为O(log2(limit))。
⑶以后再遇到I命令时，只要将初始工资x修改为x-min后再插入静态排序二叉树t即可。
procedure insert(x:longint);　　　　　　　｛新建一个初始工资为x的工资档案｝
  begin
    if x<min then exit;　　　　　　　　　　　｛若初始工资低于下限，则退出｝
    x:=x-delta;　　　　　　　　　　　　　　　　　　　　｛计算调整后的工资｝
    insert_tree(x);                       ｛将工资x插入到静态排序二叉树t｝
    end;{insert}
显然，处理I命令的时间复杂度为O(log2(limit))。
3.查找集合中第k大的数
若静态排序二叉树t的顶点树不足k，则查找失败。否则搜索量的上限为k&szlig;t[1].nodenum+1-k。
由于在静态排序二叉树t中，左子树所有顶点的值均小于根顶点的值，右子树的所有顶点的值均不小于根顶点的值，因此我们从根顶点t[1]出发，按照先左子树、后右子树的顺序进行搜索。若左子树方向上的以顶点now*2为根的子树的顶点数不足k个（k>t[now*2].nodenum），则第k大的数在now的右子树方向，k&szlig;k-t[now*2].nodenum。然后k扣除持同一工资的人数（k&szlig;k-t[now].num），并转向右子树（now&szlig;now*2+1）。
上述过程一直进行到k=0,或者持同一工资的人数大于等于k(k≤t[now].num)为止。至此，得出第k大的工资为t[now].value+delta。
procedure find(k:longint);　　　　　　　　　　　｛计算和输出排位第k的工资｝
var
  now:longint;
begin
  now:=1;
  if k>t[1].nodenum　　　　　　｛若静态排序二叉树t的顶点树不足k，则返回-1｝
     then begin writeln(-1);exit;end;{then}
  k:=t[1].nodenum+1-k;　　　　　　　　　　　　　　　　　｛计算搜索量的上限｝
  while k>0 do begin
    if (now*2<limittree) and (k<=t[now*2].nodenum)｛若now顶点的左子树存在且左子树的顶点数多于k，则沿左子树搜索下去｝
       then begin now:=now*2;continue;end;{then}
       else begin　　　｛若左子树的顶点数少于k，则搜索量减少左子树的顶点数｝
            if now*2<limittree then k:=k-t[now*2].nodenum;
            if k<=t[now].num then break;｛若now顶点持同一工资的人数不少于k，则调整后now顶点的工资为第k大｝
       end;{else}
    k:=k-t[now].num;　　　　　　　　　｛搜索量减少now顶点持同一工资的人数｝
    now:=now*2+1;　｛沿右子树搜索｝
    end;{while}
  writeln(t[now].value+delta);　　　　　　　　　　　　｛输出排拉第k的工资｝
end;{find}
显然，处理F命令的时间复杂度为O(log2(limit))。
4.主程序
有了以上的基础，很容易编出主程序：
readln(n,min);　　　　　　　　　　　　　　　　　　　　｛读命令数和工资下限｝
  delta:=0;thrownum:=0;　　　　　　　　｛工资调整量和离开公司的人数初始化｝
  init_tree;　　　　　　　　　　　　　　　　　　　　　｛建立静态排序二叉树｝
  for i:=1 to n do begin　　　　　　　　　　　　　　　　｛依次处理每条命令｝
    read(command);　　　　　　　　　　　　　　　　　｛读第i条命令的命令字｝
    readln(k);　　　　　　　　　　　　　　　　　　　｛读第i条命令的操作数｝
    case command of　　　　　　　　　　　　　　｛根据命令字的类分情形处理｝
      'I': insert(k);　　　　　　　　　　｛新建一个初始工资为x的工资档案｝
      'A': add(k);　                         ｛将新增的工资加入调整量delta｝
      'S': sub(k);｛在调整量delta中减去扣除的工资x，并从静态排序二叉树中去除工资低于下限的顶点｝
      'F': find(k);　　　　　　　　　　　　　　　｛计算和输出排位第k的工资｝
      end;{case}
  end;{for}
  writeln(thrownum)；　　　　　　　　　　　　　　　　｛输出离开公司的人数｝