Ryan_<

1482 -- 【NOI2004】郁闷的出纳员

Input

　　第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。 
　　接下来的n行，每行表示一条命令。命令可以是以下四种之一： 
　　　　
　　_（下划线）表示一个空格，I命令、A命令、S命令中的k是一个非负整数，F命令中的k是一个正整数。 
　　在初始时，可以认为公司里一个员工也没有 

把一个变量用作类似线段树中的延迟标记，不需要在每次加或者减的时候进行全部更新。在后来插入的结点中，应该当之前的延迟算进去，如果初始就小于下限的不添加，而且也不算作最后离开的人数。

在删除的时候，如果根结点小于下限，说明左子树以及根结点都小于下限，直接把右子树作为根。对新的树进行处理。

如果根结点大于下限，说明右子树也全部大于下限，对左子树进行处理，最后更新根的size。（FROM cxlove）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
const int M=100000+5;
struct data{
	int l,r,num,pro,s;
}t[M];
int n,minn;
int rt,tot,cnt,delta;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
    return x*f;
}
void update(int p)
{
	t[p].s=t[t[p].l].s+t[t[p].r].s+1;
}
void Zig(int &p)
{
	int k=t[p].r;
	t[p].r=t[k].l;
	t[k].l=p;
	t[k].s=t[p].s;//整棵子树的大小没有改变，只是根节点变换
	update(p);
	p=k;//根节点改为k
}
void Zag(int &p)
{
	int k=t[p].l;
	t[p].l=t[k].r;
	t[k].r=p;
	t[k].s=t[p].s;
	update(p);
	p=k;
}
void Insert(int &p,int x)
{
	if(p==0)
	{
		tot++;p=tot;
		t[p].pro=rand();
		t[p].num=x;
		t[p].s=1;
		return;
	}
	t[p].s++;
	if(x<t[p].num)
	{
		Insert(t[p].l,x);
		if(t[t[p].l].pro<t[p].pro) Zag(p);
	}
	else
	{
		Insert(t[p].r,x);
		if(t[t[p].r].pro<t[p].pro) Zig(p);
	}
}
int Del(int &p,int x)
{
	int k;//记录上层递归删除节点数
	if(!p) return 0;
	if(x<=t[p].num)//一定要加=
	{
		k=Del(t[p].l,x);
		t[p].s-=k;
		return k;
	}
	else
	{
		k=t[t[p].l].s+1;
		p=t[p].r;
		return k+Del(p,x);
	}
}
int Findk(int p,int k)
{
	if(t[t[p].l].s+1==k) return t[p].num+delta;
	else if(t[t[p].l].s+1<k) return Findk(t[p].r,k-t[t[p].l].s-1);//减去的1是根节点
	else return Findk(t[p].l,k);
}
int main()
{
	char ch[1];
	int x;
	rt=0;tot=0;cnt=0;
//	srand(1);
	n=read();minn=read();
	while(n--)
	{
		scanf("%s%d",ch,&x);//不要加&
		if(ch[0]=='I') if(x>=minn) Insert(rt,x-delta);
		if(ch[0]=='A') delta+=x;
		if(ch[0]=='S')
		{
			delta-=x;
			cnt+=Del(rt,minn-delta);
		}
		if(ch[0]=='F')
		{
			if(x>t[rt].s) puts("-1");
			else printf("%d\n",Findk(rt,t[rt].s-x+1));
		}
	}
	printf("%d\n",cnt);
	return 0;
}

treap模板已写熟，向SBT迈进

各种写法提交了n次..%%%Gvv