1 #include<cstdio>  2 #include<cmath>  3 #include<algorithm>  4 #include<cstring>  5 using namespace std;  6 #define N 201001  7 struct Point{int v,p;}tmp[N];  8 bool operator < (const Point &a,const Point &b){return a.v<b.v;}  9 int n,m,Infu,a[N],c[N],leave, 10 en/*插入的权值数*/,en2/*离散化之后的权值种类数*/,ma[N]; 11 char op[N]; 12 int num[N],l[460],CH[12],r[460],Num,sumv[460],sum,sz,b[N],all; 13 bool delta[N]; 14 inline void R(int &x){ 15     char c=0;int f=1; 16     for(;c<‘0‘||c>‘9‘;c=getchar())if(c==‘-‘)f=-1; 17     for(x=0;c>=‘0‘&&c<=‘9‘;c=getchar())(x*=10)+=(c-‘0‘); 18     x*=f; 19 } 20 inline void P(int x) 21 { 22     if(!x){putchar(‘0‘);puts("");return;} 23     if(x<0){putchar(‘-‘);x=-x;}Num=0; 24     while(x>0)CH[++Num]=x%10,x/=10; 25     while(Num)putchar(CH[Num--]+48);puts(""); 26 } 27 void makeblock() 28 { 29     sz=sqrt(en2); if(!sz) sz=1; 30     for(sum=1;sum*sz<en2;sum++) 31       { 32           l[sum]=r[sum-1]+1; 33           r[sum]=sum*sz; 34           for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 35       } 36     l[sum]=r[sum-1]+1; 37     r[sum]=en2; 38     for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 39 } 40 void pushdown(const int &p) 41 { 42     if(delta[p]) 43       { 44           for(int i=l[p];i<=r[p];i++) b[i]=0; 45           delta[p]=0; 46       } 47 } 48 inline void Insert(const int &x){pushdown(num[x]); b[x]++; sumv[num[x]]++; all++;} 49 inline void Delete(const int &v)//删除小于等于v的所有权值  50 { 51     int used=all; pushdown(num[v]); 52     for(int i=v;i>=l[num[v]];i--) 53       { 54           sumv[num[i]]-=b[i]; 55           all-=b[i]; 56           b[i]=0; 57       } 58     for(int i=num[v]-1;i>=1;i--) if(sumv[i]) 59       { 60           delta[i]=1; 61           all-=sumv[i]; 62           sumv[i]=0; 63       } leave+=(used-all); 64 } 65 inline int Kth(const int &x) 66 { 67     int cnt=0; 68     for(int i=sum;;i--) 69       { 70         cnt+=sumv[i]; 71         if(cnt>=x) 72           { 73             cnt-=sumv[i]; 74             for(int j=r[i];;j--) 75             {cnt+=b[j]; if(cnt>=x) return j;} 76           } 77       } 78 } 79 int main() 80 { 81     R(n); R(m); 82     for(int i=1;i<=n;i++) 83       { 84           op[i]=getchar(); R(a[i]); 85           if(op[i]==‘I‘) 86             { 87                 tmp[++en].v=a[i]-Infu;//为新员工消除之前工资变化的影响  88                 tmp[en].p=en; 89             } 90           else if(op[i]==‘A‘) Infu+=a[i]; 91           else if(op[i]==‘S‘) 92           { 93               Infu-=a[i]; 94               tmp[++en].v=m-Infu-1;//每次删除<=m-Infu-1的权值  95               tmp[en].p=en; 96           } 97       } 98     sort(tmp+1,tmp+en+1); 99     ma[c[tmp[1].p]=++en2]=tmp[1].v;100     for(int i=2;i<=en;i++)101       {102           if(tmp[i].v!=tmp[i-1].v) en2++;103           ma[c[tmp[i].p]=en2]=tmp[i].v;104       } Infu=en=0; makeblock();105     for(int i=1;i<=n;i++)106       {107           if(op[i]==‘I‘) {en++; if(a[i]>=m) Insert(c[en]);}108           else if(op[i]==‘A‘) Infu+=a[i];109           else if(op[i]==‘S‘)110           {111             Infu-=a[i];112             Delete(c[++en]);113           }114           else115             {116                 if(a[i]>all) puts("-1");117                 else P(ma[Kth(a[i])]+Infu);118             }119       } P(leave);120     return 0;121 }