记录编号	173827	评测结果	AAAAAAAAAA
题目名称	[NOI 2004]郁闷的出纳员	最终得分	100
用户昵称	炎帝	是否通过	通过
代码语言	C++	运行时间	1.192 s
提交时间	2015-07-30 08:10:30	内存使用	0.38 MiB

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
using namespace std;
int jk,yu;
struct node{
	node *left,*right;
	int zhi,fix,size;
	node(){
		left=NULL,right=NULL;
		return;
	}
};
node *root;
int n,m,k,num,hjk;
char ch[3];
struct dd{
	int hao;
}jie[30020];
void jia(node *&a){
	if(!a){
		return;
	}
	a->size=1;
	if(a){
		if(a->left){
			a->size+=a->left->size;
		}
		if(a->right){
			a->size+=a->right->size;
		}
	}
	return;
}
void K_th(node *&p,int o){
	int ji=1;
	if(p->left){
		ji+=p->left->size;
	}
	if(ji==o){
		printf("%d\n",p->zhi);
		return;
	}
	if(ji>o){
		K_th(p->left,o);
	}
	if(ji<o){
		K_th(p->right,o-ji);
	}
	return;
}
void deep(node *&a,int y){
	if(!a){
		return;
	}
	a->zhi+=y;
	deep(a->left,y);
	deep(a->right,y);
	if(a->zhi<m){
		num++;
		jie[++jk].hao=a->zhi;
		return;
	}
	return;
}
void rot_l(node *&a){
	node *b=a->right;
	a->right=b->left;
	b->left=a;
	a=b;
	jia(b->left);
	return;
}
void rot_r(node *&a){
	node *b=a->left;
	a->left=b->right;
	b->right=a;
	a=b;
	jia(b->right);
	return;
}

void insert(node *&p,int d){
	if(!p){
		p=new node;
		p->fix=rand();
		p->zhi=d;
		p->size=1;
		//p->left=p->right=0;
		return;
	}
	else{
		if(d<=p->zhi){
			insert(p->left,d);
			if(p->left->fix<=p->fix){
				rot_r(p);
			}
		}
		else{
			insert(p->right,d);
			if(p->right->fix>=p->fix){
				rot_l(p);
			}
		}
	}
	jia(p);
	return;
}
void DEL(node *&a,int d){
	if(d==a->zhi){
		if(!a->left||!a->right){
			node *b=a;
			if(a->left){
				a=a->left;
			}
			else{
				a=a->right;
			}
			delete b;
		}
		else{
			if(a->left->fix<a->right->fix){
				rot_r(a);
				DEL(a->right,d);
			}
			else{
				rot_l(a);
				DEL(a->left,d);
			}
		}
	}
	else{
	 	if(a->zhi>=d){
			DEL(a->left,d);
		}
		else{
			DEL(a->right,d);
		}
	}
	jia(a);
	return;
}

int main(){
	freopen("cashier.in","r",stdin);
	freopen("cashier.out","w",stdout);
	scanf("%d%d",&n,&m);
	srand((unsigned)time(NULL));
	for(int i=1;i<=n;++i){
		scanf("%s%d",&ch,&k);
		if(ch[0]=='I'){
			hjk++;
			if(k<m){
				num++;
				yu++; 
				continue;
			}
			else{
				insert(root,k);
			}
		}
		if(ch[0]=='A'){
			deep(root,k);
		}
		if(ch[0]=='S'){
			k=-k;
			deep(root,k);
			for(int l=1;l<=jk;++l){
				k=jie[l].hao;
				DEL(root,k);
			}
			jk=0;
		}
		if(ch[0]=='F'){
			if(k>hjk-num){
				printf("%d\n",-1);
				continue;
			}
			k=hjk-num-k+1;//已建成的树是左小右大 ； 
			K_th(root,k);
		}
	}
	printf("%d",num-yu);
	//while(1);
}