1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 using namespace std;  9 const int mxn=100010; 10 int n,m; 11 int tot=0; 12 int change=0; 13 // 14 struct node{ 15     int fa,l,r; 16     int v,num; 17     int size; 18 }tr[mxn]; 19 int root,cnt; 20 void fsize(int rt){tr[rt].size=tr[tr[rt].l].size+tr[tr[rt].r].size+1;return;} 21 void zig(int &x){ 22     int y=tr[x].fa; 23     int z=tr[y].fa; 24     if(y==tr[z].l) tr[z].l=x; 25     else tr[z].r=x; 26     tr[x].fa=z; 27     tr[y].l=tr[x].r; 28     tr[tr[x].r].fa=y; 29     tr[x].r=y; 30     tr[y].fa=x; 31     fsize(y);fsize(x); 32     if(y==root)root=x; 33 } 34 void zag(int &x){ 35     int y=tr[x].fa; 36     int z=tr[y].fa; 37     if(y==tr[z].l) tr[z].l=x; 38     else tr[z].r=x; 39     tr[x].fa=z; 40     tr[y].r=tr[x].l; 41     tr[tr[x].l].fa=y; 42     tr[y].fa=x; 43     tr[x].l=y; 44     fsize(y);fsize(x); 45     if(y==root)root=x; 46 } 47 void splay(int &x,int d){ 48     while(tr[x].fa!=d){ 49         if(tr[tr[x].fa].l==x)zig(x); 50         else zag(x); 51     } 52 } 53 void insert(int k){ 54     if(!root){ 55         root=++cnt; 56         tr[cnt].num=k; 57         tr[cnt].size=1; 58         return; 59     } 60     int p=root; 61     int z; 62     while(p){ 63         z=p; 64         ++tr[p].size; 65         if(k<tr[p].num)p=tr[p].l; 66         else p=tr[p].r; 67     } 68     if(tr[z].num>k) tr[z].l=++cnt; 69     else tr[z].r=++cnt; 70     tr[cnt].num=k;tr[cnt].size=1;tr[cnt].fa=z; 71     splay(cnt,0); 72 } 73 int find(int x,int k){ 74     if(k<=tr[tr[x].r].size)return find(tr[x].r,k); 75     if(k==tr[tr[x].r].size+1)return tr[x].num; 76     return find(tr[x].l,k-tr[tr[x].r].size-1); 77 } 78 int del(int &x,int f){ 79     if(!x)return 0; 80     int k; 81     if(tr[x].num+change<m){ 82         k=del(tr[x].r,x)+tr[tr[x].l].size+1;//统计删除个数  83         tr[tr[x].r].size=tr[x].size-k; 84         x=tr[x].r;tr[x].fa=f;//用右儿子替代当前结点  85     } 86     else{ 87         k=del(tr[x].l,x); 88         tr[x].size-=k; 89     } 90     return k; 91 } 92   93 int main(){ 94     scanf("%d%d",&n,&m); 95     int i,j; 96     char op[3];int x; 97     while(n--){ 98         scanf("%s%d",op,&x); 99         switch(op[0]){100             case ‘I‘:{101                 if(x>=m)insert(x-change);102                 break;103             }104             case ‘A‘:{105                 change+=x;106                 break;107             }108             case ‘S‘:{109                 change-=x;110                 tot+=del(root,0);111                 break;112             }113             case ‘F‘:{114                 if(x>tr[root].size){printf("-1\n");}115                 else printf("%d\n",find(root,x)+change);116                 break;117             }118         }119     }120     printf("%d\n",tot);121      122     return 0;123 }