记录编号	176176	评测结果	AAAAAAAAAA
题目名称	[NOI 2004]郁闷的出纳员	最终得分	100
用户昵称	炽烈的爱	是否通过	通过
代码语言	C++	运行时间	2.596 s
提交时间	2015-08-08 07:09:16	内存使用	0.31 MiB

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
struct treapnode
{
	treapnode *left,*right;
	int value,fix,s;
	treapnode()
	{
		left=NULL;right=NULL;
		return;
	}
};
treapnode *root;
int n,m,ans,sum;
void update(treapnode * &p)
{
	if(!p)
		return;
	p->s=1;
	if(p->left)
	{
		p->s+=p->left->s;
		//printf("11\n");
	}
	if(p->right)
	{
		p->s+=p->right->s;
		//printf("22\n");
	}
	//printf("value==%d   s==%d\n",p->value,p->s);
}
void treapleft(treapnode*&a)
{
	treapnode*b=a->right;
	a->right=b->left;
	b->left=a;
	a=b;
	update(b->left);
}
void treapright(treapnode*&a)
{
	treapnode*b=a->left;
	a->left=b->right;
	b->right=a;
	a=b;
	update(b->right);
}
void treapinsert(treapnode*&p,int x)
{
	//printf("%d\n",x);
	if(!p)
	{
		p=new treapnode;
		p->value=x;
		p->fix=rand();
		p->s=1;
		//printf("%d   %d\n",p->value,p->fix);
		//system("pause");
	}
	else
		if(x<=p->value)
		{
			treapinsert(p->left,x);
			if(p->left->fix<p->fix)
			{
				treapright(p);
				//printf("right\n");
			}
		}
		else
		{
			treapinsert(p->right,x);
			if(p->right->fix<p->fix)
			{
				treapleft(p);
				//printf("left\n");
			}
			
		}
	update(p);
	return;
}
void treapdelete(treapnode*&p)
{
		if(!p->right||!p->left)
		{
			treapnode*t=p;
			if(!p->left)
				p=p->right;
			else
				p=p->left;
			delete t;
		}
		else
		{
			if(p->left->fix<p->right->value)
			{
				treapright(p);
				treapdelete(p->right);
			}
			else
			{
				treapleft(p);
				treapdelete(p->left);
			}
		}
	update(p);
}
void bstprint(treapnode*&p,int x)
{
	if(p)
	{
		p->value+=x;
		bstprint(p->left,x);
		bstprint(p->right,x);
		if(p->value<m)
		{
			treapdelete(p);
			++ans;
		}
		update(p);
	}
}
void treapfind(treapnode*p,int x)
{
	//printf("pppppppppp%d\n",x);
	
	if((!p->left)&&x==1)
	{
		printf("%d\n",p->value);
		return;	
	}
	if(!p->left)
	{
		treapfind(p->right,x-1);
		return;
	}
	if(p->left->s+1==x)
	{
		printf("%d\n",p->value);
		return;
	}
	else
	{
		if(p->left->s+1<x&&(p->right))
		{
			//printf("%d   value===%d\n",p->right->s,p->value);
			treapfind(p->right,x-p->left->s-1);
		}
		else
			if(p->left)
			{
				//printf("left===%d   value===%d\n",p->left->s,p->value);
				treapfind(p->left,x);
			}
	}
}
int main()
{
	freopen("cashier.in","r",stdin);
	freopen("cashier.out","w",stdout);
	scanf("%d%d",&n,&m);
	srand((unsigned)time(NULL));
	for(int t=1;t<=n;++t)
	{
		char ch[3];int x;
		//getchar();//getchar();
		scanf("%s%d",ch,&x);
		if(ch[0]=='I')
		{
		
			if(x>=m)
			{	
				++sum;
				treapinsert(root,x);
			}
		}
		if(ch[0]=='A')
			bstprint(root,x);
		if(ch[0]=='S')
		{
			x*=-1;
			bstprint(root,x);
		}
		if(ch[0]=='F')
		{
			if(x>sum-ans)
				printf("-1\n");
			else
			{
				x=sum-ans+1-x;
				treapfind(root,x);
			}	
		}
	}
	printf("%d\n",ans);
	//while(1);	
}