记录编号	360703	评测结果	AAAAAAAAAA
题目名称	[NOI 2004]郁闷的出纳员	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.419 s
提交时间	2016-12-31 11:39:02	内存使用	7.15 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100000*5;
int ls[maxn],rs[maxn],size[maxn],v[maxn],RT,cnt;
int n,Least,Plus;
void pushup(int rt){size[rt]=size[ls[rt]]+size[rs[rt]]+1;}
void Turn_left(int & rt){
	int t=rs[rt];
	rs[rt]=ls[t];pushup(rt);
	ls[t]=rt;pushup(t);
	rt=t;
}
void Turn_right(int & rt){
	int t=ls[rt];
	ls[rt]=rs[t];pushup(rt);
	rs[t]=rt;pushup(t);
	rt=t;
}
#define Balance_all Balance(ls[rt]);Balance(rs[rt]);Balance(rt);
void Balance(int & rt){
	if(size[ls[ls[rt]]]>size[rs[rt]]){
		Turn_right(rt);Balance_all;
		return;
	}
	if(size[rs[rs[rt]]]>size[ls[rt]]){
		Turn_left(rt);Balance_all;
		return;
	}
	if(size[rs[ls[rt]]]>size[rs[rt]]){
		Turn_left(ls[rt]);Turn_right(rt);Balance_all;
		return;
	}
	if(size[ls[rs[rt]]]>size[ls[rt]]){
		Turn_right(rs[rt]);Turn_left(rt);Balance_all;
		return;
	}
}
#undef Balance_all
void Insert(int & rt,int date){
	if(rt==0){
		rt=++cnt;size[rt]=1;v[rt]=date;
		return;
	}
	if(date<v[rt])Insert(ls[rt],date);
	else Insert(rs[rt],date);
	pushup(rt);
	Balance(rt);
}
int Del(int & rt){
	if(!rt)return 0;
	int tot=0;
	if(v[rt]+Plus<Least){
		tot+=size[ls[rt]]+1;size[rt]-=tot;ls[rt]=0;
		int num=Del(rs[rt]);tot+=num;size[rt]-=num;
		size[rs[rt]]=size[rt];rt=rs[rt];
		Balance(rt);
	}
	else {
		tot=Del(ls[rt]);size[rt]-=tot;
		Balance(rt);
	}
	return tot;
}
int Get_date(int rt,int th){
	if(size[rs[rt]]+1==th)return v[rt];
	if(size[rs[rt]]+1>th)return Get_date(rs[rt],th);
	else return Get_date(ls[rt],th-size[rs[rt]]-1);
}
void Init();
int main(){
    freopen("cashier.in","r",stdin);freopen("cashier.out","w",stdout);
    Init();
    getchar();getchar();
    return 0;
}
void Init(){
	scanf("%d%d",&n,&Least);int ans=0;
	for(int i=1;i<=n;i++){
		char type;int date;scanf(" %c%d",&type,&date);
		if(type=='I'){
			if(date<Least)continue;
			Insert(RT,date-Plus);
		}
		else if(type=='A')Plus+=date;
		else if(type=='S'){
			Plus-=date;ans+=Del(RT);
		}
		else if(type=='F'){
			if(size[RT]<date)puts("-1");
			else printf("%d\n",Get_date(RT,date)+Plus);
		}
	} 
	printf("%d\n",ans);
}