[NOI2004]郁闷的出纳员（Treap）

【题解】

Treap水过

注意：对于null结点，不能进行 o->s = o->ch[0]->s + 1 + o->ch[1]->s 操作，一定要考虑此问题

【代码】

#include<stdio.h>
#include<stdlib.h>
int ans=0;
struct Node
{
	Node* ch[2];
	int v,r,s;
	int cmp_v(int x) const
	{
		if(x==v) return -1;
		if(x<v) return 0;
		return 1;
	}
	int cmp_s(int x) const
	{
		if( x == ch[0]->s + 1 ) return -1;
		if( x <= ch[0]->s ) return 0;
		return 1;
	}
};
Node *root,*null;
void init()
{
	null=new Node();
	null->ch[0] = null->ch[1] = NULL;
	null->v = null->r = null->s = 0;
	root=null;
}
void gets(Node* &o) 
{
	o->s = o->ch[0]->s + o->ch[1]->s + 1;
}
void xz(Node* &o,int d)
{
	Node* k=o->ch[d^1];
	o->ch[d^1]=k->ch[d];
	k->ch[d]=o;
	gets(o);
	gets(k);
	o=k;
}
void tj(Node* &o,int x)
{
	int d;
	if(o==null)
	{
		o=new Node();
		o->ch[0] = o->ch[1] = null;
		o->v=x;
		o->r=rand();
		o->s=1;
		return;
	}
	o->s++;
	d=o->cmp_v(x);
	if(d==-1) d=0;
	tj(o->ch[d],x);
	if( o->ch[d]->r < o->r ) xz(o,d^1);
}
void sc(Node* &o,int x)
{
	int d;
	if(o==null) return;
	d=o->cmp_v(x);
	if(d!=1)
	{
		sc(o->ch[0],x);
		gets(o);
		return;
	}
	ans += o->ch[0]->s + 1;
	o=o->ch[1];
	sc(o,x);
}
int find(Node* &o,int x)
{
	int d=o->cmp_s(x);
	if(d==-1) return o->v;
	if(d==1) x -= o->ch[0]->s + 1;
	return find(o->ch[d],x);
}
int main()
{
	srand(233);
	char opt;
	int n,min,x,add=0;
	scanf("%d%d",&n,&min);
	init();
	for(;n>0;n--)
	{
		scanf("\n%c %d",&opt,&x);
		if(opt=='I')
			if(x>=min) tj(root,x-add);
		if(opt=='A') add+=x;
		if(opt=='S')
		{
			add-=x;
			sc(root,min-add);
		}
		if(opt=='F')
		{
			if( root->s >= x ) printf("%d\n",find(root,root->s-x+1)+add);
			else printf("-1\n");
		}
	}
	printf("%d",ans);
	return 0;
}