一万年以后终于调过了这题
这道题主要是维护一个有序的集合(吧),所以使用平衡树(我这里用(Splay))
记录一个变量(ff)(雾),表示所有工资的变化量
对于(I)操作,如果初始工资大于等于下界(mi)就加进去,加进去时工资(k)要减去(ff)(我写这道题,把(k-ff)当成初始工资判断了,然后搞到今天才A mmp)
对于(A)操作,(ff+=k)
对于(S)操作,(ff-=k),还要考虑删点.我们可以从根出发,对于每个节点判断,小于下界(mi)就把左子树和自己的(size)加入答案,把右子树接到当前节点的父亲上去,然后删掉左子树和自己,继续处理;或者加入一个权值为(mi-ff-1)的点,旋到根,答案加上左子树和根节点(size)再-1,然后删去
最后一个操作就是平衡树第(k)大,不解释
略丑的代码
// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#define LL long long
#define il inline
#define re register
using namespace std;
il LL rd()
{
re LL x=0,w=1;re char ch;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int tot=0,ans,n,mi,ff;
struct Spl
{
int rt;
Spl(){rt=0;}
struct nn
{
int ch[2],sz,fa,cs,x;
nn(){x=0,cs=1,sz=fa=ch[0]=ch[1]=0;}
}tr[110000];
void pushup(int x){tr[x].sz=tr[tr[x].ch[0]].sz+tr[tr[x].ch[1]].sz+tr[x].cs;}
void rot(int x)
{
int y=tr[x].fa,z=tr[y].fa;
int yy=(tr[y].ch[1]==x),zz=(tr[z].ch[1]==y);
tr[z].ch[zz]=x,tr[x].fa=z;
tr[y].ch[yy]=tr[x].ch[yy^1],tr[tr[x].ch[yy^1]].fa=y;
tr[x].ch[yy^1]=y,tr[y].fa=x;
pushup(y),pushup(x);
}
void spl(int x,int en)
{
while(tr[x].fa!=en)
{
int y=tr[x].fa,z=tr[y].fa;
if(z!=en) (tr[y].ch[1]==x)^(tr[z].ch[1]==y)?rot(x):rot(y);
rot(x);
}
if(!en) rt=x;
}
void inst(int x)
{
int now=rt;
while(tr[now].ch[x>tr[now].x]&&tr[now].x!=x)
now=tr[now].ch[x>tr[now].x];
if(tr[now].x==x) ++tr[now].cs;
else
{
++tot;
tr[tot].sz=1;
tr[now].ch[x>tr[now].x]=tot;
tr[tot].fa=now;
tr[tot].x=x;
now=tot;
}
spl(now,0);
}
void find(int x)
{
int now=rt;
while(tr[now].ch[x>tr[now].x]&&tr[now].x!=x)
now=tr[now].ch[x>tr[now].x];
if(now) spl(now,0);
}
int ftnt(int x,int ffa)
{
find(x);
if((tr[rt].x>x&&ffa)||(tr[rt].x<x&&!ffa)) return rt;
int now=tr[rt].ch[ffa];
while(tr[now].ch[ffa^1]) now=tr[now].ch[ffa^1];
return now;
}
void del(int x)
{
int xx=ftnt(x,0),yy=ftnt(x,1);
spl(xx,0),spl(yy,xx);
tr[yy].ch[0]=0;
pushup(yy);pushup(xx);
}
int kth(int x)
{
int now=rt;
while(1)
{
if(x<=tr[tr[now].ch[0]].sz) now=tr[now].ch[0];
else if(x>tr[tr[now].ch[0]].sz+tr[now].cs) x-=tr[tr[now].ch[0]].sz+tr[now].cs,now=tr[now].ch[1];
else return now;
}
}
il int pd(int x){return tr[tr[x].fa].ch[1]==x;}
il void work()
{
int xx=mi-ff-1;
inst(xx);
ans+=tr[tr[rt].ch[0]].sz+tr[rt].cs-1;
rt=tr[rt].ch[1];
tr[tr[rt].fa].ch[1]=-1;
tr[rt].fa=0;
}
}a;
int main()
{
a.inst(998244353);
n=rd();mi=rd();
int zz=0;
for(int i=1;i<=n;i++)
{
char cc[4];
scanf("%s",cc);
int x=rd();
if(cc[0]=='I')
{
if(x<mi) continue;
x-=ff,a.inst(x),++zz;
}
else if(cc[0]=='A') ff+=x;
else if(cc[0]=='S') ff-=x,a.work();
else x<=zz-ans?printf("%d
",a.tr[a.kth(zz-ans-x+1)].x+ff):printf("-1
");
}
printf("%d
",ans);
return 0;
}