★★★   输入文件：cashier.in   输出文件：cashier.out   简单对比

　　　　　　　　　　　　　　　　　　　　时间限制：1 s   内存限制：128 MB

【问题描述】

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 10I 60I 70S 50F 2I 30S 15A 5F 1F 2

【样例输出】

1020-12

【约定】

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

题解：

　　对于每次工资的加减，如果加工资，让工资的下线MIN减去这个数，如果减工资，让工资的下线MIN加上这个数，就是用一种相对运动的思想。

　　再记录一个delta变量，来处理新加入的员工。

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 using namespace std; 10 typedef long long LL; 11 const LL maxn=100010; 12 char s[5]; 13 LL root,tot,N,MIN,sum,delta; 14 LL key[maxn],lc[maxn],rc[maxn],siz[maxn]; 15 void r_rotate(LL &rt){ 16 LL k=lc[rt]; 17 lc[rt]=rc[k]; 18 rc[k]=rt; 19 siz[k]=siz[rt]; 20 siz[rt]=siz[lc[rt]]+siz[rc[rt]]+1; 21 rt=k; 22 } 23 void l_rotate(LL &rt){ 24 LL k=rc[rt]; 25 rc[rt]=lc[k]; 26 lc[k]=rt; 27 siz[k]=siz[rt]; 28 siz[rt]=siz[lc[rt]]+siz[rc[rt]]+1; 29 rt=k; 30 } 31 void Maintain(LL &rt,bool flag){ 32 if(flag==false){ 33 if(siz[lc[lc[rt]]]>siz[rc[rt]]) r_rotate(rt); 34 else if(siz[rc[lc[rt]]]>siz[rc[rt]]){ 35 l_rotate(lc[rt]); 36 r_rotate(rt); 37 } 38 else return ; 39 } 40 else{ 41 if(siz[rc[rc[rt]]]>siz[lc[rt]]) l_rotate(rt); 42 else if(siz[lc[rc[rt]]]>siz[lc[rt]]){ 43 r_rotate(rc[rt]); 44 l_rotate(rt); 45 } 46 else return ; 47 } 48 Maintain(lc[rt],0); Maintain(rc[rt],1); 49 Maintain(rt,1); Maintain(rt,0); 50 } 51 void insert(LL &rt,LL v){ 52 if(rt==0){ 53 rt=++tot; 54 siz[rt]=1; 55 lc[rt]=rc[rt]=0; 56 key[rt]=v; 57 return ; 58 } 59 siz[rt]++; 60 if(v<=key[rt]) insert(lc[rt],v); 61 else insert(rc[rt],v); 62 Maintain(rt,1); Maintain(rt,0); 63 } 64 LL Delete(LL &rt,LL v){ 65 LL ans; 66 siz[rt]--; 67 if(v==key[rt]||(v
             
              key[rt]&&rc[rt]==0)){ 68 ans=key[rt]; 69 if(lc[rt]==0||rc[rt]==0) rt=lc[rt]+rc[rt]; 70 else key[rt]=Delete(lc[rt],key[rt]+1); 71 return ans; 72 } 73 else if(v
              
               key[rt]) return find(rc[rt],v); 87 } 88 LL pred(LL &rt,LL v){ 89 if(rt==0) return v; 90 if(v<=key[rt]) return pred(lc[rt],v); 91 else{ 92 LL ans=pred(rc[rt],v); 93 if(ans==v) return key[rt]; 94 return ans; 95 } 96 } 97 void Clear(){ 98 for(;;){ 99 LL k=pred(root,MIN);100 if(find(root,k)==true&&k
              
             
            
           
          
         
        
       
      
     

 　　下面再来一发splay版的，但是splay的删除操作要十分小心，情况一定要考虑全面，还有边界情况，我跪了整整一天半。。。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 using namespace std; 9 typedef long long LL; 10 const LL maxn=100010; 11 LL key[maxn],lc[maxn],rc[maxn],fa[maxn],siz[maxn]; 12 LL tot,root; 13 char s[5]; 14 LL N,MIN,sum,delta; 15 void update(LL x){ 16 siz[x]=siz[lc[x]]+1+siz[rc[x]]; 17 } 18 void r_rotate(LL x){ 19 LL y=fa[x]; 20 lc[y]=rc[x]; 21 if(rc[x]!=0) fa[rc[x]]=y; 22 fa[x]=fa[y]; 23 if(y==lc[fa[y]]) lc[fa[y]]=x; 24 else rc[fa[y]]=x; 25 fa[y]=x; rc[x]=y; 26 update(x); update(y); 27 } 28 void l_rotate(LL x){ 29 LL y=fa[x]; 30 rc[y]=lc[x]; 31 if(lc[x]!=0) fa[lc[x]]=y; 32 fa[x]=fa[y]; 33 if(y==lc[fa[y]]) lc[fa[y]]=x; 34 else rc[fa[y]]=x; 35 fa[y]=x; lc[x]=y; 36 update(x); update(y); 37 } 38 void splay(LL x,LL s){ 39 LL p; 40 while(fa[x]!=s){ 41 p=fa[x]; 42 if(fa[p]==s){ 43 if(x==lc[p]) r_rotate(x); 44 else l_rotate(x); 45 break; 46 } 47 if(x==lc[p]){ 48 if(p==lc[fa[p]]) r_rotate(p),r_rotate(x); 49 else r_rotate(x),l_rotate(x); 50 } 51 else{ 52 if(p==rc[fa[p]]) l_rotate(p),l_rotate(x); 53 else l_rotate(x),r_rotate(x); 54 } 55 } 56 if(s==0) root=x; 57 update(x); 58 } 59 void New_node(LL &x,LL fath,LL v){ //建立新节点 60 x=++tot; 61 lc[x]=rc[x]=0; siz[x]=1; 62 fa[x]=fath; 63 key[x]=v; 64 } 65 void insert(LL v){ //插入新节点 66 if(root==0){ 67 New_node(root,0,v); 68 return ; 69 } 70 LL p,x=root; 71 while(x!=0){ 72 p=x; 73 if(v<=key[x]) siz[x]++,x=lc[x]; 74 else siz[x]++,x=rc[x]; 75 } 76 if(v<=key[p]) New_node(lc[p],p,v); 77 else New_node(rc[p],p,v); 78 splay(tot,0); 79 } 80 LL find(LL v){ //查找在这棵树中键值为v的节点 81 LL x=root; 82 while(x!=0){ 83 if(v
            
             key[x]) x=rc[x]; 85 else if(v==key[x]){ 86 splay(x,0); 87 return x; 88 } 89 } 90 return -1; 91 } 92 LL getmax(LL x){ //找到以x为根的最大值 93 while(rc[x]!=0) x=rc[x]; 94 return x; 95 } 96 LL getmin(LL x){ //找到以x为根的最小值 97 while(lc[x]!=0) x=lc[x]; 98 return x; 99 }100 LL getpre(LL x){ //找到节点x的前驱 101 splay(x,0);102 if(lc[x]==0) return -1;103 return getmax(lc[x]);104 }105 LL getne(LL x){ //找到节点x的后继106 splay(x,0);107 if(rc[x]==0) return -1; 108 return getmin(rc[x]);109 }110 LL join(LL s1,LL s2){ //把以s1和s2为根的子树合并，返回根 111 if(s1==0||s2==0){112 if(s1==0&&s2==0){113 rc[0]=0;114 return 0; 115 }116 if(s1==0){117 rc[fa[s2]]=0; rc[0]=s2; fa[s2]=0;118 siz[root]=1;119 return s2; 120 }121 else{122 lc[fa[s1]]=0; rc[0]=s1; fa[s1]=0;123 siz[root]=1;124 return s1;125 }126 }127 LL p=getmax(s1);//由getmax()函数可知，p要么是根的左孩子，要么是其父亲的右孩子, p肯定没有右孩子 128 if(p==lc[fa[p]]){ //p是根的左孩子129 if(lc[p]!=0) //如果p有左孩子 130 lc[fa[p]]=lc[p],fa[lc[p]]=fa[p];//把p的左孩子接到父节点上 131 else lc[fa[p]]=0;132 }133 else{ //p是其父亲的右孩子134 if(lc[p]!=0) //如果p有左孩子 135 rc[fa[p]]=lc[p],fa[lc[p]]=fa[p];//把p的左孩子接到父节点上136 else rc[fa[p]]=0;137 }138 update(fa[p]);//更新p的父亲s的iz值 139 LL rt=fa[s1];140 lc[rt]=rc[rt]=0; siz[rt]=1;//删去原根 141 if(s1!=p) lc[p]=s1,fa[s1]=p; //p的左孩子变成原根的左孩子142 rc[p]=s2; fa[s2]=p; //p的左孩子变成原根的右孩子143 fa[p]=0; rc[0]=p;144 update(p);145 return p;146 }147 void Delete(LL v){ //删除一个键值为v的节点 148 LL x=find(v);149 root=join(lc[x],rc[x]);150 }151 152 LL findkth(LL x,LL k){ //在以x为根的树中找第 k大 153 if(siz[lc[x]]+1==k) return key[x];154 if(siz[lc[x]]+1>k) return findkth(lc[x],k);155 return findkth(rc[x],k-siz[lc[x]]-1);156 }157 158 LL pred(LL rt,LL v){ //返回比 v小的最大的数 159 if(rt==0) return v;160 if(v<=key[rt]) return pred(lc[rt],v);161 else{162 LL ans=pred(rc[rt],v);163 if(ans==v) return key[rt]; 164 return ans;165 }166 }167 void Clear(){168 for(;;){169 LL k=pred(root,MIN);170 if(find(k)!=-1&&k
            
           
          
         
        
       
      
     

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 using namespace std; 9 typedef long long LL; 10 const LL maxn=100010; 11 LL key[maxn],lc[maxn],rc[maxn],fa[maxn],siz[maxn]; 12 LL tot,root; 13 char s[5]; 14 LL N,MIN,sum,delta; 15 void update(LL x){ 16 siz[x]=siz[lc[x]]+1+siz[rc[x]]; 17 } 18 void r_rotate(LL x){ 19 LL y=fa[x]; 20 lc[y]=rc[x]; 21 if(rc[x]!=0) fa[rc[x]]=y; 22 fa[x]=fa[y]; 23 if(y==lc[fa[y]]) lc[fa[y]]=x; 24 else rc[fa[y]]=x; 25 fa[y]=x; rc[x]=y; 26 update(x); update(y); 27 } 28 void l_rotate(LL x){ 29 LL y=fa[x]; 30 rc[y]=lc[x]; 31 if(lc[x]!=0) fa[lc[x]]=y; 32 fa[x]=fa[y]; 33 if(y==lc[fa[y]]) lc[fa[y]]=x; 34 else rc[fa[y]]=x; 35 fa[y]=x; lc[x]=y; 36 update(x); update(y); 37 } 38 void splay(LL x,LL s){ 39 LL p; 40 while(fa[x]!=s){ 41 p=fa[x]; 42 if(fa[p]==s){ 43 if(x==lc[p]) r_rotate(x); 44 else l_rotate(x); 45 break; 46 } 47 if(x==lc[p]){ 48 if(p==lc[fa[p]]) r_rotate(p),r_rotate(x); 49 else r_rotate(x),l_rotate(x); 50 } 51 else{ 52 if(p==rc[fa[p]]) l_rotate(p),l_rotate(x); 53 else l_rotate(x),r_rotate(x); 54 } 55 } 56 if(s==0) root=x; 57 update(x); 58 } 59 void New_node(LL &x,LL fath,LL v){ //建立新节点 60 x=++tot; 61 lc[x]=rc[x]=0; siz[x]=1; 62 fa[x]=fath; 63 key[x]=v; 64 } 65 void insert(LL v){ //插入新节点 66 if(root==0){ 67 New_node(root,0,v); 68 return ; 69 } 70 LL p,x=root; 71 while(x!=0){ 72 p=x; 73 if(v<=key[x]) siz[x]++,x=lc[x]; 74 else siz[x]++,x=rc[x]; 75 } 76 if(v<=key[p]) New_node(lc[p],p,v); 77 else New_node(rc[p],p,v); 78 splay(tot,0); 79 } 80 LL find(LL v){ //查找在这棵树中键值为v的节点 81 LL x=root; 82 while(x!=0){ 83 if(v
            
             key[x]) x=rc[x]; 85 else if(v==key[x]){ 86 splay(x,0); 87 return x; 88 } 89 } 90 return -1; 91 } 92 LL getmax(LL x){ //找到以x为根的最大值 93 while(rc[x]!=0) x=rc[x]; 94 return x; 95 } 96 LL getmin(LL x){ //找到以x为根的最小值 97 while(lc[x]!=0) x=lc[x]; 98 return x; 99 }100 LL getpre(LL x){ //找到节点x的前驱 101 splay(x,0);102 if(lc[x]==0) return -1;103 return getmax(lc[x]);104 }105 LL getne(LL x){ //找到节点x的后继106 splay(x,0);107 if(rc[x]==0) return -1; 108 return getmin(rc[x]);109 }110 LL join(LL s1,LL s2){ //把以s1和s2为根的子树合并，返回根 111 if(s1==0||s2==0){112 if(s1==0&&s2==0){113 rc[0]=0;114 return 0; 115 }116 if(s1==0){117 rc[fa[s2]]=0; rc[0]=s2; fa[s2]=0;118 siz[root]=1;119 return s2; 120 }121 else{122 lc[fa[s1]]=0; rc[0]=s1; fa[s1]=0;123 siz[root]=1;124 return s1;125 }126 }127 LL p=getmax(s1);//由getmax()函数可知，p要么是根的左孩子，要么是其父亲的右孩子, p肯定没有右孩子 128 if(p==lc[fa[p]]){ //p是根的左孩子129 if(lc[p]!=0) //如果p有左孩子 130 lc[fa[p]]=lc[p],fa[lc[p]]=fa[p];//把p的左孩子接到父节点上 131 else lc[fa[p]]=0;132 }133 else{ //p是其父亲的右孩子134 if(lc[p]!=0) //如果p有左孩子 135 rc[fa[p]]=lc[p],fa[lc[p]]=fa[p];//把p的左孩子接到父节点上136 else rc[fa[p]]=0;137 }138 update(fa[p]);//更新p的父亲s的iz值 139 LL rt=fa[s1];140 lc[rt]=rc[rt]=0; siz[rt]=1;//删去原根 141 if(s1!=p) lc[p]=s1,fa[s1]=p; //p的左孩子变成原根的左孩子142 rc[p]=s2; fa[s2]=p; //p的左孩子变成原根的右孩子143 fa[p]=0; rc[0]=p;144 update(p);145 return p;146 }147 void Delete(LL v){ //删除一个键值为v的节点 148 LL x=find(v);149 root=join(lc[x],rc[x]);150 }151 152 LL findkth(LL x,LL k){ //在以x为根的树中找第 k大 153 if(siz[lc[x]]+1==k) return key[x];154 if(siz[lc[x]]+1>k) return findkth(lc[x],k);155 return findkth(rc[x],k-siz[lc[x]]-1);156 }157 158 LL pred(LL rt,LL v){ //返回比 v小的最大的数 159 if(rt==0) return v;160 if(v<=key[rt]) return pred(lc[rt],v);161 else{162 LL ans=pred(rc[rt],v);163 if(ans==v) return key[rt]; 164 return ans;165 }166 }167 void Clear(){168 for(;;){169 LL k=pred(root,MIN);170 if(find(k)!=-1&&k