洛谷$P$1486 郁闷的出纳员 $[NOI2004]$ $splay$
正解:$splay$
解题报告:
依然先考虑要呲呲些什么操作鸭$QwQ$
其实就只要一个删除区间,一个查询第$k$大,还一个插入就欧克?
删除区间的话直接旋转下根什么的然后直接把子树删了就好$QwQ$
查询第$k$大和$insert$是基操不说$QwQ$
然后还一个就集体扣除工资?本来一般这种还要考虑加个$ad[]$的$tag$,,,但因为这题太水了$QwQ$所以所有$add$操作的对象都是全员鸭$QwQ$所以直接开个变量记录所有人的修改就成,然后删除区间和$insert$的值相应改点儿就好$QwQ$
$over$,,,?
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#define gc getchar()
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
const int N=500000+100,inf=1e9;
int n,mm,ad,peo,as,rt,nod_cnt;
bool gdgs=1;
struct node{int ch[2],fa,val,cnt,sz;il void pre(ri x,ri fat){ch[0]=ch[1]=0;fa=fat;val=x;cnt=sz=1;}}tr[N];
il int read()
{
rc ch=gc;ri x=0;rb y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il char rd(){rc ch=gc;while(ch!='I' && ch!='A' && ch!='S' && ch!='F')ch=gc;return ch;}
il void pushup(ri x){tr[x].sz=tr[tr[x].ch[0]].sz+tr[tr[x].ch[1]].sz+tr[x].cnt;}
il void rotate(ri x)
{
ri fa=tr[x].fa,grdfa=tr[fa].fa;bool op1=tr[fa].ch[1]==x,op2=tr[grdfa].ch[1]==fa;
tr[grdfa].ch[op2]=x;tr[x].fa=grdfa;
tr[fa].ch[op1]=tr[x].ch[op1^1];tr[tr[x].ch[op1^1]].fa=fa;
tr[fa].fa=x;tr[x].ch[op1^1]=fa;
pushup(fa);pushup(x);
}
il void splay(ri x,ri goal)
{
while(tr[x].fa!=goal)
{
ri fa=tr[x].fa,grdfa=tr[fa].fa;
if(grdfa!=goal)(tr[fa].ch[0]==x)^(tr[grdfa].ch[0]==fa)?rotate(x):rotate(fa);
rotate(x);
}
if(!goal)rt=x;
}
il void insert(ri x)
{
ri nw=rt,fa=0;
while(nw && tr[nw].val!=x)fa=nw,nw=tr[nw].ch[x>tr[nw].val];//,printf("nw=%d\n",nw);
if(nw){++tr[nw].cnt;splay(nw,0);return;}
nw=++nod_cnt;if(fa)tr[fa].ch[x>tr[fa].val]=nod_cnt;tr[nw].pre(x,fa);
splay(nw,0);
}
il void fd(ri x)
{
ri nw=rt;if(!nw)return;
while(tr[nw].ch[tr[nw].val<x] && tr[nw].val!=x)nw=tr[nw].ch[tr[nw].val<x];
splay(nw,0);
}
il int ask_val(ri x)
{
if(x<=0 || tr[rt].sz<x)return -1-ad;
ri nw=rt;
while(gdgs)
{
if(tr[nw].cnt+tr[tr[nw].ch[0]].sz<x)x-=tr[tr[nw].ch[0]].sz+tr[nw].cnt,nw=tr[nw].ch[1];
else if(tr[tr[nw].ch[0]].sz>=x)nw=tr[nw].ch[0];
else return tr[nw].val;
}
}
il int ask_lst(ri x)
{
fd(x);ri nw=tr[rt].ch[1];
if(tr[rt].val>=x)return rt;
while(tr[nw].ch[0])nw=tr[nw].ch[0];
return nw;
}
il void delet(ri x)
{
ri nw=ask_lst(mm-ad);
splay(nw,0);
as+=tr[tr[rt].ch[0]].sz;peo-=tr[tr[rt].ch[0]].sz;
tr[tr[rt].ch[0]].sz=tr[tr[rt].ch[0]].cnt=0;
tr[rt].ch[0]=0;
tr[0].sz=0;
pushup(rt);
}
int main()
{
n=read();mm=read();insert(inf);
while(n--)
{
rc ch=rd();ri x=read();
switch(ch)
{
case 'I':if(x>=mm)insert(x-ad),++peo;break;
case 'A':ad+=x;break;
case 'S':ad-=x;delet(mm-ad);break;
case 'F':printf("%d\n",ask_val(peo-x+1)+ad);break;
}
}
printf("%d\n",as);
return 0;
}