1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<cstdio> 5 #include<cstdlib> 6 #include<algorithm> 7 #include<cmath> 8 #include<ctime> 9 using namespace std;10 const int maxn=101000;11 const int inf=100000000;12 char ch;13 int n,minn=0,delet=0,x,sum=0,root=0,len=0,all=0;14 struct node{15     int m,v,siz;16     int ch[2];17     int cmp(int x){return m>x?0:1;}18 }e[maxn<<2];19 void countsiz(int &x,int d){20     int k=e[x].ch[d];21     e[x].siz=e[x].siz-e[k].siz+e[e[k].ch[d^1]].siz;22     e[k].siz=e[e[k].ch[d]].siz+e[x].siz+1;23 }24 void rotate(int &x,int d){25     countsiz(x,d);26     int k=e[x].ch[d];27     e[x].ch[d]=e[k].ch[d^1];28     e[k].ch[d^1]=x;29     x=k;30 }31 void insert(int &x,int m){32     if(x==0){x=++len;e[x].m=m;e[x].v=rand();e[x].siz=1;return;}33     int d=e[x].cmp(m);34     insert(e[x].ch[d],m);35     e[x].siz=e[e[x].ch[0]].siz+e[e[x].ch[1]].siz+1;36     if(e[e[x].ch[d]].v>e[x].v)rotate(x,d);37 }38 void found(int m){39     if(m<minn)return;40     all++;41     insert(root,m-delet);42 }43 void dfs(int &x){44     if(x==0)return;45     if(e[x].m+delet>=minn){dfs(e[x].ch[0]);e[x].siz=e[e[x].ch[0]].siz+e[e[x].ch[1]].siz+1;return;}46     if(e[x].m+delet<minn){47         if(e[x].ch[1]){48             rotate(x,1);49             dfs(x);50             if(x==0)return;51             for(int d=0;d<2;d++)if(e[e[x].ch[d]].v>e[x].v)rotate(x,d);52             e[x].siz=e[e[x].ch[0]].siz+e[e[x].ch[1]].siz+1;53         }54         else{55             sum+=e[x].siz;56             x=0;57         }58     }59 }60 void add(int x){61     delet+=x;62     if(x<0)dfs(root);63 }64 int dfs(int x,int k,int right){65     int r=e[x].ch[1];66     if(x==0)return -inf;67     if(right+e[r].siz==k)return e[x].m;68     if(right+e[r].siz>k)return dfs(r,k,right);69     if(right+e[r].siz<k)return dfs(e[x].ch[0],k,right+e[r].siz+1);70 }71 void find(int k){72     int p=dfs(root,k-1,0);73     printf("%d\n",p==-inf?-1:p+delet);74 }75 void work(){76     srand(time(0));77     scanf("%d%d",&n,&minn);78     while(n--){79         scanf(" %c %d",&ch,&x);80         if(ch==‘I‘)found(x);81         if(ch==‘A‘)add(x);82         if(ch==‘S‘)add(-x);83         if(ch==‘F‘)find(x);84     }85     cout<<sum<<endl;86 }87 int main(){88     work();89 }