P1486 [NOI2004] 郁闷的出纳员

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int Q,Min,d,root,tot,ans,Size[N],cnt[N],fa[N],s[N][2],w[N];

void pushup(int u){
	Size[u]=Size[s[u][0]]+Size[s[u][1]]+cnt[u];
}

void Rotate(int u){
	int f=fa[u],g=fa[fa[u]];
	int k=s[f][1]==u;
	s[g][s[g][1]==f]=u,fa[u]=g;
	s[f][k]=s[u][k^1],fa[s[u][k^1]]=f;
	s[u][k^1]=f,fa[f]=u;
	pushup(f);
	pushup(u);
}

void splay(int u,int t){
	while(fa[u]!=t){
		int f=fa[u],g=fa[fa[u]];
		if(g!=t){
			if((s[f][1]==u)^(s[g][1]==f)) Rotate(u);
			else Rotate(u);
		}
		Rotate(u);
	}
	if(!t) root=u;
}

void Insert(int v){
	int u=root,f=0;
	while(u&&v!=w[u]){f=u;u=s[u][v>w[u]];}
	if(u) cnt[u]++;
	else{
		u=++tot;
		if(f) s[f][v>w[f]]=u;
		fa[u]=f,w[u]=v,Size[u]=cnt[u]=1;
	}
	splay(u,0);
}

void Find(int v){
	int u=root;
	if(!u) return ;
	while(s[u][v>w[u]]&&v!=w[u]) u=s[u][v>w[u]];
	splay(u,0);
}

int Next(int v,int opt){
	Find(v);
	int u=root;
	if((w[u]>v&&opt)||(w[u]<v&&!opt)) return u;
	u=s[u][opt];
	while(s[u][opt^1]) u=s[u][opt^1];
	return u;
}

int Get(int k){
	int u=root;
	if(k>Size[u]) return -1;
	while(true){
		if(k>Size[s[u][1]]+cnt[u]){
			k-=Size[s[u][1]]+cnt[u];
			u=s[u][0];
		}
		else if(k<=Size[s[u][1]]) u=s[u][1];
		else{splay(u,0);return w[u];}
	}
}

void Delete(int v){
	Insert(v);
	int tail=Next(v,1);
	splay(tail,0);
	ans+=Size[s[tail][0]]-1;
	s[tail][0]=0;
	pushup(tail);
}

int main(){
	scanf("%d%d",&Q,&Min);
	Insert(INT_MAX);
	while(Q--){
		getchar();
		char c=getchar();
		int x;
		scanf("%d",&x);
		switch(c){
			case 'I':{
				if(x>=Min) Insert(x-d);
				break;
			}
			case 'A':d+=x;break;
			case 'S':{
				d-=x;
				Delete(Min-d);
				break;
			}
			case 'F':{
				printf("%d\n",Get(x)+d);
				break;
			}
		}
	}
	printf("%d",ans);
	return 0;
}