文件详细信息

下载本文件

本文件的大小为 1541 字节。

#include<cstdio>
inline int max(const int a,const int b){
	return a>b?a:b;
}
inline int min(const int a,const int b){
	return a<b?a:b;
}
const int maxn=50005,maxm=50005;
struct Data{
	int x,full;
};
int n,m,x,val,a[maxn],T[maxn<<2];
char op;
void pushup(int u){
	if(T[u<<1]==0&&T[u<<1|1]==0)T[u]=0;
	else T[u]=1;
}
void modify(int u,int l,int r){
	if(l==r){
		T[u]=val;
		return;
	}
	int m=(l+r)>>1;
	if(x<=m)modify(u<<1,l,m);
	else modify(u<<1|1,m+1,r);
	pushup(u);
}
Data query_left(int u,int l,int r,int x){
	if(T[u]==0)return(Data){min(r,x)-l+1,1};
	if(l==r)return(Data){0,0};
	int m=(l+r)>>1;
	if(x<=m)return query_left(u<<1,l,m,x);
	Data _r=query_left(u<<1|1,m+1,r,x);
	if(_r.full){
		Data _l=query_left(u<<1,l,m,x);
		return(Data){_l.x+_r.x,_l.full};
	}else return _r;
}
Data query_right(int u,int l,int r,int x){
	if(T[u]==0)return(Data){r-max(l,x)+1,1};
	if(l==r)return(Data){0,0};
	int m=(l+r)>>1;
	if(x>m)return query_right(u<<1|1,m+1,r,x);
	Data _l=query_right(u<<1,l,m,x);
	if(_l.full){
		Data _r=query_right(u<<1|1,m+1,r,x);
		return(Data){_l.x+_r.x,_r.full};
	}else return _l;
}
int stack[maxm],top;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		do op=getchar();
		while(op!='D'&&op!='Q'&&op!='R');
		if(op=='D'){
			scanf("%d",&x);
			stack[++top]=x;
			a[x]=val=1;
			modify(1,1,n);
		}else if(op=='Q'){
			scanf("%d",&x);
			if(a[x])puts("0");
			else printf("%d\n",query_left(1,1,n,x-1).x+query_right(1,1,n,x+1).x+1);
		}else if(top>0){
			x=stack[top--];
			a[x]=val=0;
			modify(1,1,n);
		}
	}
	return 0;
}