文件详细信息

下载本文件

本文件的大小为 2218 字节。

#include<cstdio>
void read(int&num){
	bool flag=true;
	int ch=getchar();
	num=0;
	while(ch<48||ch>57){
		if(ch=='-')flag=false;
		ch=getchar();
	}
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	flag||(num=-num);
}
void write(int a){
	static int ch[20],cnt;
	cnt=0;
	if(a<0)a=-a,putchar('-');
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|'0',a/=10;
	while(cnt)putchar(ch[--cnt]);
	putchar('\n');
}
void get_char(int&x){
	x=getchar();
	while(x==' '||x=='\r'||x=='\n')x=getchar();
}
const int maxn=100005;
int n,min,op,x,tag,tot;
struct Node{
	Node*fa,*ch[2];
	int val,cnt,size;
}T[maxn],*rt=T;
void clear(Node*u){
	u->fa=u->ch[0]=u->ch[1]=T;
	u->val=-1;
	u->cnt=u->size=0;
}
void maintain(Node*u){
	u->size=u->cnt+u->ch[0]->size+u->ch[1]->size;
}
int get(const Node*x){
	return x->fa->ch[1]==x;
}
void rotate(Node*x){
	Node*y=x->fa,*z=y->fa;
	int k=get(x);
	y->ch[k]=x->ch[k^1];
	if(y->ch[k]!=T)y->ch[k]->fa=y;
	x->ch[k^1]=y;
	y->fa=x;
	x->fa=z;
	if(z!=T)z->ch[z->ch[1]==y]=x;
	maintain(y);
	maintain(x);
}
void splay(Node*x){
	for(Node*f=x->fa;f=x->fa,f!=T;rotate(x))
		if(f->fa!=T)
			rotate(get(x)==get(f)?f:x);
	rt=x;
}
void insert(int k){
	if(rt==T){
		rt=T+(++tot);
		clear(rt);
		rt->val=k;
		rt->cnt=1;
		maintain(rt);
		return;
	}
	Node*u=rt,*f=T;
	while(true){
		if(u->val==k){
			u->cnt++;
			maintain(u);
			maintain(f);
			splay(u);
			return;
		}
		f=u;
		u=u->ch[u->val<k];
		if(u==T){
			u=T+(++tot);
			clear(u);
			u->fa=f;
			f->ch[f->val<k]=u;
			u->val=k;
			u->cnt=1;
			maintain(u);
			maintain(f);
			splay(u);
			break;
		}
	}
}
Node*kth(int k){
	Node*u=rt;
	while(true){
		if(u==T)return T;
		if(u->ch[0]!=T&&k<=u->ch[0]->size)u=u->ch[0];
		else{
			k-=u->ch[0]->size+u->cnt;
			if(k<=0){
				splay(u);
				return u;
			}
			u=u->ch[1];
		}
	}
}
int ans,cnt;
int main(){
	read(n),read(min);
	clear(rt);
	for(int i=1;i<=n;i++){
		get_char(op),read(x);
		if(op=='I'){
			if(x>=min){
				insert(x-tag);
				cnt++;
			}
		}else if(op=='A')tag+=x;
		else if(op=='S'){
			tag-=x;
			insert(min-tag-1);
			ans+=rt->ch[0]->size+rt->cnt-1;
			rt=rt->ch[1];
			rt->fa=T;
		}else{
			if(x<=cnt-ans)write(kth(cnt-ans-x+1)->val+tag);
			else write(-1);
		}
	}
	write(ans);
	return 0;
}