1503: [NOI2004]郁闷的出纳员
题目：传送门
题解：
修改操作一共不超过100
直接暴力在伸展树上修改
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
struct node
{
int d,c,n,f,son[];
}tr[];int len,root,ans;
void add(int d,int f)
{
len++;tr[len].d=d;tr[len].n=tr[len].c=;
tr[len].son[]=tr[len].son[]=;tr[len].f=f;
if(d<tr[f].d)tr[f].son[]=len;
else tr[f].son[]=len;
}
void update(int x)
{
int lc=tr[x].son[],rc=tr[x].son[];
tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
}
int findip(int d)
{
int x=root;
while(tr[x].d!=d)
{
if(d<tr[x].d)
{
if(tr[x].son[]==)break;
else x=tr[x].son[];
}
else
{
if(tr[x].son[]==)break;
else x=tr[x].son[];
}
}
return x;
}
void rotate(int x,int w)
{
int f=tr[x].f,ff=tr[f].f;
int r,R;
r=tr[x].son[w],R=f;
tr[R].son[-w]=r;
if(r!=)tr[r].f=R; r=x,R=ff;
if(tr[R].son[]==f)tr[R].son[]=r;
else tr[R].son[]=r;
tr[r].f=R; r=f,R=x;
tr[R].son[w]=r;
tr[r].f=R; update(f);update(x);
}
void splay(int x,int rt)
{
while(tr[x].f!=rt)
{
int f=tr[x].f,ff=tr[f].f;
if(ff==rt)
{
if(tr[f].son[]==x)rotate(x,);
else rotate(x,);
}
else
{
if(tr[ff].son[]==f && tr[f].son[]==x)rotate(f,),rotate(x,);
else if(tr[ff].son[]==f && tr[f].son[]==x)rotate(f,),rotate(x,);
else if(tr[ff].son[]==f && tr[f].son[]==x)rotate(x,),rotate(x,);
else if(tr[ff].son[]==f && tr[f].son[]==x)rotate(x,),rotate(x,);
}
}
if(rt==)root=x;
}
void ins(int d)
{
if(root==)
{
add(d,);root=len;
return ;
}
int x=findip(d);
if(tr[x].d==d)
{
tr[x].n++;
update(x);
splay(x,);
}
else
{
add(d,x);
update(x);
splay(len,);
}
}
void del(int d)
{
int x=findip(d);if(tr[x].d!=d)return ;
ans+=tr[x].n;splay(x,);
if(tr[x].son[]== && tr[x].son[]==){root=;len=;}
else if(tr[x].son[]!= && tr[x].son[]==){root=tr[x].son[];tr[root].f=;}
else if(tr[x].son[]== && tr[x].son[]!=){root=tr[x].son[];tr[root].f=;}
else
{
int p=tr[x].son[];
while(tr[p].son[]!=)p=tr[p].son[];
splay(p,x); int r=tr[x].son[],R=p;
tr[R].son[]=r;
tr[r].f=R; root=p;tr[root].f=;
update(root);
}
}
void findshuzi(int k)
{
int x=root;
while()
{
int lc=tr[x].son[],rc=tr[x].son[];
if(k<=tr[lc].c)x=lc;
else if(k>tr[lc].c+tr[x].n)k-=tr[lc].c+tr[x].n,x=rc;
else break;
}
printf("%d\n",tr[x].d);
}
int n,m,sum,sc[];
void jia(int x,int k)
{
tr[x].d+=k;
if(tr[x].son[]!=)jia(tr[x].son[],k);
if(tr[x].son[]!=)jia(tr[x].son[],k);
}
void jian(int x,int k)
{
tr[x].d-=k;if(tr[x].d<m)sc[++sum]=x;
if(tr[x].son[]!=)jian(tr[x].son[],k);
if(tr[x].son[]!=)jian(tr[x].son[],k);
}
char st[];
int main()
{
scanf("%d%d",&n,&m);ans=;
len=;root=;
for(int i=;i<=n;i++)
{
sum=;
int x;scanf("%s%d",st+,&x);
if(st[]=='I')
{
if(x<m)continue;
ins(x);
}
else if(st[]=='A')jia(root,x);
else if(st[]=='S')
{
jian(root,x);
for(int j=;j<=sum;j++)del(tr[sc[j]].d);
}
else
{
if(tr[root].c<x)printf("-1\n");
else findshuzi(tr[root].c-x+);
}
}
printf("%d\n",ans);
return ;
}