1503 [noi2004]郁闷的出纳员

#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
typedef long long LL;
const int maxn = 500055;
using namespace std;
int size[maxn],data[maxn],c[maxn][2],root,fa[maxn],tot,dnum,cnum;
int m,n,w;
void (){
	size[0] = 0;
	
	data[1] = 1000000000;
	c[1][0]=c[1][1] = 0;
	size[1] = 1;
	root=1;
	tot=1;
	dnum = cnum = 0;
}
void update(int x){
	if(!x) return ;
	size[x]=size[c[x][0]]+size[c[x][1]]+1;
}
void rotate(int x){
	int y=fa[x],k = (c[y][0]==x);
	fa[x] = fa[y];
	if (fa[y]) c[fa[y]][c[fa[y]][1]==y] = x;
	c[y][!k] = c[x][k];
	fa[c[x][k]] = y;
	c[x][k] = y;
	fa[y] = x;
	update(y);update(x);
}
void splay(int x,int g){
	for (int y=fa[x];y!=g;rotate(x),y=fa[x]){
		if(fa[y]!=g) rotate((c[y][0]==x)==(c[fa[y]][0]==y)?y:x);
	}
	if (!g) root=x;
}
void Insert(int key){
	int y = root;
	while(c[y][data[y]+w<key+w]) y = c[y][data[y]+w<key+w];
	data[++tot] = key+w-w;
	c[tot][0] = c[tot][1] = 0;
	if (y) c[y][data[y]+w<key+w] = tot;
	fa[tot] = y;
	size[tot] = 1;
	splay(tot,0);
}
void NOT(){
	int y,z;
	for (y=root;y;){
		if (data[y]+w>m) z = y,y = c[y][0];	else 
		if (data[y]+w==m) z = y,y = c[y][0]; else
		y=c[y][1];
	}
	
	y=z;
	splay(y,0); 
	dnum += size[c[y][0]];
	cnum -= size[c[y][0]];
	fa[c[y][0]] = 0;
	size[c[y][0]] = 0;
	c[y][0] = 0;
	update(y);
}
int findkth(int x){
	int y=root;
	while(x){
		if(x==size[c[y][0]]+1) return y; else
		if(x>size[c[y][0]]+1) x-=size[c[y][0]]+1,y=c[y][1]; else
		y=c[y][0];
	}
	return y;
}
int main(){
	init();
	int x;
	scanf("%d%d",&n,&m);
	w=0;
	for (int i=1;i<=n;i++){
		char c = getchar();
		while(c!='I'&&c!='A'&&c!='S'&&c!='F')c=getchar();
		scanf("%d",&x);
		if(c=='I'){
			x-=w;
			if(x+w>=m){
				cnum++;
				Insert(x);
			}// else
			//	dnum++;
			//题目太坑，一开始不加入的不算离开！。 
		}
		if (c=='A')	w+=x; 
		if (c=='S')	w-=x,NOT();
		if (c=='F'){
			x = cnum - x + 1;
			if (x<=0||x>cnum) puts("-1"); else printf("%dn",data[findkth(x)]+w);
		}
	}
	printf("%dn",dnum);
	return 0;
}