记录编号	217973	评测结果	AWAWWWWWWW
题目名称	[NOI 2004]郁闷的出纳员	最终得分	20
用户昵称	一個人的雨	是否通过	未通过
代码语言	C++	运行时间	1.384 s
提交时间	2016-01-07 06:53:45	内存使用	0.70 MiB

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=0x7fffffff/2-1;
struct Splay{
	Splay *f,*c[2];
	int key,num,sz;
	bool isr;
}*nil=new Splay((Splay){0,0,0,0,0,0,0}),*Stmp=new Splay((Splay){nil,nil,nil,inf,1,1,1}),*root=Stmp;
int n,dow,cnt=0,a[100000];
int tot=0,now=0;

void push_up(Splay *p){
	p->sz=p->c[0]->sz+p->c[1]->sz+p->num;
}

void zig(Splay *p,bool D){
	Splay *y=p->f; p->f=y->f;
	if (y->isr){y->isr=0;p->isr=1;}
	if (p->f->c[0]==y) p->f->c[0]=p;
	else p->f->c[1]=p;
	y->c[D]=p->c[!D]; y->c[D]->f=y;
	y->f=p; p->c[!D]=y; 
	push_up(y); push_up(p);
}

void splay(Splay *p){
	bool D;
	while (!p->isr){
		D=p->f->c[1]==p;
		if (!p->f->isr&&D==(p->f->f->c[1]==p->f)) zig(p->f,D);
		zig(p,D);
	}root=p;
}

inline Splay *insert(Splay *p,int key){
	if (p->key<dow) a[++cnt]=p->key;
	if (p->key==key) return p;
	if (p->key<key)
	    if (p->c[1]!=nil) return insert(p->c[1],key);
	    else return p->c[1]=new Splay((Splay){p,nil,nil,key,0,0,0});
	if (p->c[0]!=nil) return insert(p->c[0],key);
	else return p->c[0]=new Splay((Splay){p,nil,nil,key,0,0,0});
}

void mul(Splay *p,int val){
	p->key+=val; 
	if (p->key<=dow) a[++cnt]=p->key;
	if (p->c[0]!=nil) mul(p->c[0],val);
	if (p->c[1]!=nil) mul(p->c[1],val);
}

void Delete(){
	Splay *sn; root->c[1]->isr=1;
	sn=root->c[1];
	while (sn->c[0]!=nil) sn=sn->c[0];
	splay(sn);
	root->c[0]=root->f->c[0];
	root->sz+=root->f->c[0]->sz;
	root->c[0]->f=root;
	delete(root->f); root->f=nil;
}

Splay *findkth(Splay *p,int k){
	if (p->key<dow) a[++cnt]=p->key;
	if (p->c[0]->sz>=k) return findkth(p->c[0],k);
	if (p->sz-p->c[1]->sz>=k) return p;
	return findkth(p->c[1],k-p->c[0]->sz-p->num);
}

Splay *find(Splay *p,int key){
	if (p->key==key) return p;
	if (p->key<key) return find(p->c[1],key);
	return find(p->c[0],key);
}

int main(){
	freopen("cashier.in","r",stdin);
	freopen("cashier.out","w",stdout);
	scanf("%d%d",&n,&dow);
	nil->f=nil; nil->c[0]=nil; nil->c[1]=nil; 
	for (int i=1;i<=n;++i){
		char ch; int x; cin>>ch;
		switch(ch){
			case 'I':
				scanf("%d",&x); now++;
				cnt=0; splay(insert(root,x));
				root->num++; root->sz++; tot+=cnt;
				for (int j=1;j<=cnt;++j){
					splay(find(root,a[j]));
					if (!(--root->num)){
						Delete(); now--;
					}else --root->sz,now--;//!!!!!!!
				} break;
			case 'A':
				scanf("%d",&x); 
				cnt=0; mul(root,x); tot+=cnt;
				for (int j=1;j<=cnt;++j){
					splay(find(root,a[j]));
					if (!(--root->num)){
						Delete(); now--;
					}else --root->sz,now--;//!!!!!!!
				}break;
			case 'S':
				scanf("%d",&x); x=-x;
				cnt=0; mul(root,x); tot+=cnt;
				for (int j=1;j<=cnt;++j){
					splay(find(root,a[j]));
					if (!(--root->num)){
						Delete(); now--;
					}else --root->sz,now--;//!!!!!!!
				}break;
			case 'F':
				scanf("%d",&x); 
				if (x>now){
					printf("%d\n",-1);break;
				} x=now-x+1; 
				splay(findkth(root,x));
				printf("%d\n",root->key);
				break;
		}
	} printf("%d",tot);
}