记录编号	283692	评测结果	AAAAAAAAAA
题目名称	[NOI 2004]郁闷的出纳员	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	1.089 s
提交时间	2016-07-15 10:49:15	内存使用	1.84 MiB

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=100001;
int lower;//最低工资；
int add_pay=0;
int c_num=0;
int front=0;
struct Node
{
	int key,size,llink,rlink;
}number[maxn];
void LeftRotate(int &x)//左旋
{
	int y=number[x].rlink;
	if(y==0)return;
	number[x].rlink=number[y].llink;
	number[y].llink=x;
	number[y].size=number[x].size;
	number[x].size=number[number[x].llink].size+number[number[x].rlink].size+1;
	x=y;
}
void RightRotate(int &x)//右旋 
{
	int y=number[x].llink;
	if(y==0)return;
	number[x].llink=number[y].rlink;
	number[y].rlink=x;
	number[y].size=number[x].size;
	number[x].size=number[number[x].llink].size+number[number[x].rlink].size+1;
	x=y;
}
void Maintain(int &root,bool flag)//维护SBT树 
{
	if(!root)return;
	if(flag)
	{
		if(number[root].llink&&number[number[root].llink].llink&&
		(!number[root].rlink||number[number[number[root].llink].llink].size>number[number[root].rlink].size))
		{
			RightRotate(root);
		}
		else if(number[root].llink&&number[number[root].llink].rlink&&
		(!number[root].rlink||number[number[number[root].llink].rlink].size>number[number[root].rlink].size))
		{
			LeftRotate(number[root].llink);
			RightRotate(root);
		}
		else return;
	}
	else
	{
		if(number[root].rlink&&number[number[root].rlink].rlink&&
		(!number[root].llink||number[number[number[root].rlink].rlink].size>number[number[root].llink].size))
		{
			LeftRotate(root);
		}
		else if(number[root].rlink&&number[number[root].rlink].llink&&
		(!number[root].llink||number[number[number[root].rlink].llink].size>number[number[root].llink].size))
		{
			RightRotate(number[root].rlink);
			LeftRotate(root);
		}
		else return;
	}
	Maintain(number[root].llink,true);
	Maintain(number[root].rlink,false);
	Maintain(root,true);
	Maintain(root,false);
}
int Delete(int &root)
{
	int t=0,sum=0;
	if(!root)return root;
	if(number[root].key+add_pay<lower)
	{
		sum+=number[number[root].llink].size+1;
		number[root].size-=sum;
		number[root].llink=0;
		t=Delete(number[root].rlink);
		sum+=t;
		number[root].size-=t;
		number[number[root].rlink].size=number[root].size;
		root=number[root].rlink;
	}
	else
	{
		t=Delete(number[root].llink);
		sum=t;
		number[root].size-=t;
	}
	return sum;
}
void Insert(int &root,int x)
{
	if(!root)
	{
		root=++front;
		number[root].key=x;
		number[root].size=1;
	}
	else
	{
		number[root].size++;
		Insert(x<=number[root].key?number[root].llink:number[root].rlink,x);
		Maintain(root,x<=number[root].key);
	}
}
int Select(int R,int x)//返回第x大的元素
{
	if(number[R].rlink==0)
	{
		number[number[R].rlink].size=0;
	} 
	int r=number[number[R].rlink].size+1;
	if(x<r)return Select(number[R].rlink,x);
	else
	{
		if(x>r)
		{
			return Select(number[R].llink,x-r);
		}
		if(x==r)
		{
			return number[R].key;
		}
	}
}
int main()
{
	freopen("cashier.in","r",stdin);
	freopen("cashier.out","w",stdout);
	int N;
	char command;
	int pay,root=0;
	int i;
	cin>>N>>lower;
	for(i=1;i<=N;i++)
	{
		cin>>command>>pay;
		if(command=='I')
		{
			if(pay>=lower)
			{
				Insert(root,pay-add_pay);
			}
		}
		if(command=='F')
		{
			if(pay>number[root].size)
			{
				cout<<-1<<endl;
			}
			else
			{
				cout<<Select(root,pay)+add_pay<<endl;
			}
		}
		if(command=='A')
		{
			add_pay+=pay;
		}
		if(command=='S')
		{
			add_pay-=pay;
			c_num+=Delete(root);
		}
	}
	cout<<c_num<<endl;
	return 0;
	
}