1. 我不是新八... 我不會吐槽...

    2. 用任何平衡樹寫都好.... 我是用來練splay的~~~(鄙視我這個弱菜有意思么)

    3. 為毛剛進(jìn)公司就離開的人不需要統(tǒng)計(jì).... 題目里面也沒說啊... 害得我查了一晚上... 最后在插入的時(shí)候加個判斷就過了...

    插入和查詢就是splay的基本操作了~

    刪除半?yún)^(qū)間我是把(工資下限-1)插入到splay當(dāng)中再旋到樹根(splay經(jīng)典操作)然后刪除左子樹和樹根。

    工資的升降可以直接更改工資下限，將更改的總量記錄一下~

    

    splay可以只寫zig和zig-zig操作，zig-zag可以歸約掉... Orzzzzzz...... 一下子好寫了很多

    維護(hù)size域我是從下到上維護(hù)的...因?yàn)樾枰聅ize的只有x的直系祖先，所以旋到樹根的過程相當(dāng)于更新了...

    我終于會寫splay了... 好高欣~

   

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 using namespace std;
  5 #define re(i,n) for(int i =0; i< n; i++)
  6 const int N = 100005;
  7 const int inf = ~0u>>2;
  8 int sum,splaysz,temp;
  9 // template 
 10 struct node {
 11     int p,chd[2],sz,mul,v;
 12     node(int P=0,int val=0){
 13         chd[0] = chd[1] = 0; sz = 0; mul = 1;
 14         p = P, v = val;
 15     }
 16 } tree[N];
 17 inline void sc(int y, int x, int p){tree[y].chd[p] = x, tree[x].p = y;}
 18 inline void upd(int x){ tree[x].sz = tree[tree[x].chd[0]].sz + tree[tree[x].chd[1]].sz+tree[x].mul;}
 19 inline void rot(int x){
 20     int y = tree[x].p;
 21     int w = tree[y].chd[1] == x;
 22     sc(tree[y].p,x,tree[tree[y].p].chd[1] == y);
 23     sc(y,tree[x].chd[w^1], w);
 24     sc(x,y,w^1);
 25     upd(y); upd(x);
 26 }
 27 void splay(int x,int rt){
 28     while(tree[x].p != rt){
 29         int y = tree[x].p;
 30         int w = tree[y].chd[1] == x;
 31         if(tree[y].p != rt && tree[tree[y].p].chd[w] == y) rot(y);
 32         rot(x);
 33     }
 34 }
 35 // operate 
 36 void ins(int val){
 37     if(tree[0].chd[0] == 0) {tree[++splaysz] = node(0,val); tree[0].chd[0] = splaysz; upd(splaysz); return;}
 38     int now = tree[0].chd[0];
 39     while(1){
 40         if(val == tree[now].v){
 41             tree[now].mul++;
 42             upd(now);
 43             splay(now,0);
 44             return ;
 45         }
 46         int w = val > tree[now].v;
 47         if(tree[now].chd[w]) now = tree[now].chd[w];
 48         else {
 49             tree[++splaysz] = node(now,val); tree[now].chd[w] = splaysz;
 50             upd(splaysz);
 51             splay(splaysz,0);
 52             return ;
 53         }
 54     }
 55 }
 56 void find(int pos,int k){
 57     if (tree[pos].sz < k) {
 58         puts("-1");
 59         return ;
 60     }
 61     int x = tree[pos].chd[0];
 62     if(tree[x].sz>=k) find(x,k);
 63     else if(tree[x].sz + tree[pos].mul>=k) {
 64         printf("%d\n",tree[pos].v-temp);
 65     }
 66     else find(tree[pos].chd[1], k - tree[x].sz - tree[pos].mul);
 67 }
 68 void del(){
 69     int r = tree[0].chd[0];
 70     int x = tree[r].chd[1];
 71     sum += tree[r].sz - tree[x].sz -1;
 72     tree[x].p = 0 , tree[0].chd[0] = x;
 73 }
 74 // main
 75 int main(){
 76     int n,m,x;
 77     char ch[10];
 78     while(cin >>n >>m){
 79         sum = temp = splaysz = 0;
 80         tree[0] = node(0,inf);
 81         re(i,n){
 82             scanf("%s%d",ch,&x);
 83             switch(ch[0]){
 84                 case 'I' :
 85                     if(x >= m)
 86                         ins(x + temp);
 87                     break;
 88                 case 'S' :
 89                     temp += x;
 90                     ins(m + temp-1); del();
 91                     break;
 92                 case 'A' :
 93                     temp -= x;
 94                     break;
 95                 case 'F' :
 96                     if(tree[tree[0].chd[0]].sz < x) puts("-1");
 97                     else find(tree[0].chd[0],tree[tree[0].chd[0]].sz - x + 1);
 98                     break;
 99             }
100         }
101         printf("%d\n",sum);
102     }
103 }
104