记录编号	173108	评测结果	AAAAAAAAAA
题目名称	[NOI 2004]郁闷的出纳员	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	1.068 s
提交时间	2015-07-27 21:51:59	内存使用	0.31 MiB

#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <vector>

struct Node{
	Node *left,*right;
	int val,fix,s;
	Node(){
		left=NULL;right=NULL;
		return;
	}
};

std::vector<int> rd;

Node *root;

int Min,n,k,num,Sum,c;

char inp[5];

void Update(Node *&p){
    if(!p){
        return;
    }
	p->s=1;
	if(p->left){
		p->s+=p->left->s;
	}
	if(p->right){
		p->s+=p->right->s;
	}
	return;
}

void Rturn(Node *&a){
	Node *b=a->left;
	a->left=b->right;
	b->right=a;
	a=b;
	Update(b->right);
    return;
}

void Lturn(Node *&a){
	Node *b=a->right;
	a->right=b->left;
	b->left=a;
	a=b;
	Update(b->left);
	return;
}

void Del(Node *&p){
    if(k==p->val){
 	  if(!p->left||!p->right){
    		Node *t=p;
    		if(p->left){
    			p=p->left;
    		}
    		else{
    			p=p->right;
    		}
    		delete t;
    	}
    	else{
    		if(p->left->fix < p->right->fix){
    			Rturn(p);
    			Del(p->right);
    		}
    		else{
    			Lturn(p);
    			Del(p->left);
    		}
    	}       
    }
    else{
        if(p->val>=k){
            Del(p->left);
        }
        else{
            Del(p->right);
        }
    }
    Update(p);
	return;
}

void dfs(Node *&p){
	if(!p){
		return;
	}
	p->val+=k;
	dfs(p->left);
	dfs(p->right);
	if(p->val<Min){
		rd.push_back(p->val);num++;return;
	}
	return;
}

void Insert(Node *&p){
	if(!p){
		p=new Node;
		p->val=k;
		p->fix=rand();
		p->s=1;
		return;
	}
	else if(k<=p->val){
		Insert(p->left);
		if(p->left->fix < p->fix){
			Rturn(p);
		}
	}
	else{
		Insert(p->right);
		if(p->right->fix < p->fix){
			Lturn(p);
		}
	}
    Update(p);
	return;
}

void Find(Node *p,int r){
	int Rank=1;
	if(p->left){
		Rank+=p->left->s;
	}
	if(Rank==r){
		printf("%d",p->val);
		return;
	}
	else if(Rank<r){
		Find(p->right,r-Rank);
	}
	else{
		Find(p->left,r);
	}
	return;
}

int main(){
	freopen("cashier.in","r",stdin);
	freopen("cashier.out","w",stdout);
	srand((unsigned)time(NULL));
	scanf("%d%d",&n,&Min);
	for(int i=1;i<=n;i++){
		scanf("%s%d",inp,&k);
		if(inp[0]=='I'){
			Sum++;
			if(k<Min){
				num++;c++;
			}
			else{
				Insert(root);
			}
		}
		else if(inp[0]=='A'){
			dfs(root);
		}
		else if(inp[0]=='S'){
            k=-k;
			dfs(root);
			int sz=rd.size();
			for(int i=0;i<sz;i++){
                k=rd[i];Del(root);
            }rd.clear();
		}
		else{
			if(k>Sum-num){
				puts("-1");
			}
			else{
				k=Sum-num-k+1;
				Find(root,k);
			}
		}
	}
	printf("%d",num-c);
	return 0;
}