权值分块，离散化非常蛋疼，只能离散化搞……
需要支持操作：删除<=某个值得所有权值==打标记 O(sqrt(n))
码长和我的平衡树差不多……速度快3倍左右。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 201001
struct Point{int v,p;}tmp[N];
bool operator < (const Point &a,const Point &b){return a.v<b.v;}
int n,m,Infu,a[N],c[N],leave,
en/*插入的权值数*/,en2/*离散化之后的权值种类数*/,ma[N];
char op[N];
int num[N],l[],CH[],r[],Num,sumv[],sum,sz,b[N],all;
bool delta[N];
inline void R(int &x){
char c=;int f=;
for(;c<''||c>'';c=getchar())if(c=='-')f=-;
for(x=;c>=''&&c<='';c=getchar())(x*=)+=(c-'');
x*=f;
}
inline void P(int x)
{
if(!x){putchar('');puts("");return;}
if(x<){putchar('-');x=-x;}Num=;
while(x>)CH[++Num]=x%,x/=;
while(Num)putchar(CH[Num--]+);puts("");
}
void makeblock()
{
sz=sqrt(en2); if(!sz) sz=;
for(sum=;sum*sz<en2;sum++)
{
l[sum]=r[sum-]+;
r[sum]=sum*sz;
for(int i=l[sum];i<=r[sum];i++) num[i]=sum;
}
l[sum]=r[sum-]+;
r[sum]=en2;
for(int i=l[sum];i<=r[sum];i++) num[i]=sum;
}
void pushdown(const int &p)
{
if(delta[p])
{
for(int i=l[p];i<=r[p];i++) b[i]=;
delta[p]=;
}
}
inline void Insert(const int &x){pushdown(num[x]); b[x]++; sumv[num[x]]++; all++;}
inline void Delete(const int &v)//删除小于等于v的所有权值
{
int used=all; pushdown(num[v]);
for(int i=v;i>=l[num[v]];i--)
{
sumv[num[i]]-=b[i];
all-=b[i];
b[i]=;
}
for(int i=num[v]-;i>=;i--) if(sumv[i])
{
delta[i]=;
all-=sumv[i];
sumv[i]=;
} leave+=(used-all);
}
inline int Kth(const int &x)
{
int cnt=;
for(int i=sum;;i--)
{
cnt+=sumv[i];
if(cnt>=x)
{
cnt-=sumv[i];
for(int j=r[i];;j--)
{cnt+=b[j]; if(cnt>=x) return j;}
}
}
}
int main()
{
R(n); R(m);
for(int i=;i<=n;i++)
{
op[i]=getchar(); R(a[i]);
if(op[i]=='I')
{
tmp[++en].v=a[i]-Infu;//为新员工消除之前工资变化的影响
tmp[en].p=en;
}
else if(op[i]=='A') Infu+=a[i];
else if(op[i]=='S')
{
Infu-=a[i];
tmp[++en].v=m-Infu-;//每次删除<=m-Infu-1的权值
tmp[en].p=en;
}
}
sort(tmp+,tmp+en+);
ma[c[tmp[].p]=++en2]=tmp[].v;
for(int i=;i<=en;i++)
{
if(tmp[i].v!=tmp[i-].v) en2++;
ma[c[tmp[i].p]=en2]=tmp[i].v;
} Infu=en=; makeblock();
for(int i=;i<=n;i++)
{
if(op[i]=='I') {en++; if(a[i]>=m) Insert(c[en]);}
else if(op[i]=='A') Infu+=a[i];
else if(op[i]=='S')
{
Infu-=a[i];
Delete(c[++en]);
}
else
{
if(a[i]>all) puts("-1");
else P(ma[Kth(a[i])]+Infu);
}
} P(leave);
return ;
}