1. 题目

传送门=￣ω￣=

2. 题解

好吧其实我知道可以不写 push_down 直接记录当前更改总量的。

但是为了练习 splay，也就打了带下穿标记的啦=￣ω￣=

但是，，，气死我惹！！！改了我好久啊，WA了不知道多少多少次，最后发现，，，是因为如果一个人初始工资就低于最低工资，那么这个人不算进入了公司！也就是那个人不能算进离开公司的人数中！

真是坑啊=。=

好吧，反正就是个 splay 整棵树加减，改 root 的标记就行了。

至于踢出公司的话，每次把工资最少的提到根节点，然后判断这个人是否工资少于最少工资，是的话就删除根节点。不断执行这个操作，直到工资最少的人工资多于最少工资。当然也可以区间删除（删除子树），懒得写了，一个一个删也不会慢多少。

代码：

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct N{int f,s[2],d,c,tag,sz;}e[100005];
int n,m,root,cnt,K,ans;
char opt[5];
bool pos(int a){return e[e[a].f].s[1]==a;}
void pup(int a){e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+e[a].c;}
void pdown(int a)
{
    int l=e[a].s[0],r=e[a].s[1],t=e[a].tag;
    if(t!=0)
    {
        if(l)e[l].tag+=t,e[l].d+=t;
        if(r)e[r].tag+=t,e[r].d+=t;
        e[a].tag=0;
    }
}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);
    pdown(f),pdown(a);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    pup(f),pup(a);
}
void splay(int a,int t)
{
    for(;e[a].f!=t;rot(a))if(e[e[a].f].f!=t)
        if(pos(a)^pos(e[a].f))rot(a);
        else rot(e[a].f);
    if(!t)root=a;
}
void insert(int d,int fa,int&a)
{
    if(!a){a=++cnt,e[a].f=fa,e[a].d=d,e[a].sz=e[a].c=1,splay(a,0);return;}
    pdown(a);
    if(d>e[a].d)insert(d,a,e[a].s[0]);
    else if(d<e[a].d)insert(d,a,e[a].s[1]);
    else e[a].c++,e[a].sz++,splay(a,0);
}
void update(int k){if(root)e[root].tag+=k,e[root].d+=k;}
int find_by_order(int k)
{
    int a=root;
    while(a)
    {
        pdown(a);
        if(k<=e[e[a].s[0]].sz)a=e[a].s[0];
        else
        {
            k-=e[e[a].s[0]].sz+e[a].c;
            if(k<=0)return a;
            a=e[a].s[1];
        }
    }
    return 0;
}
void check()
{
    while(e[root].sz)
    {
        int a=find_by_order(e[root].sz);
        if(splay(a,0),e[a].d>=m)break;
        ans+=e[a].c,e[e[a].s[0]].f=0,root=e[a].s[0];
    }
}
int main()
{
    IN(n),IN(m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",opt),IN(K);
        if(opt[0]=='I'){if(K<m)continue;insert(K,0,root),check();}
        else if(opt[0]=='A')update(K);
        else if(opt[0]=='S')update(-K),check();
        else    if(K>e[root].sz)puts("-1");
                    else printf("%d\n",e[find_by_order(K)].d);
    }
    printf("%d\n",ans);
    return 0;
}