评测记录

#include<bits/stdc++.h>
using namespace std;
int root=0,ll=1,v[100005],l[100005],r[100005],sz[100005],w[100005],n,m;
bool bj[100005];
int New(int vv)
{
	v[ll]=vv;
	sz[ll]=1;
	w[ll]=rand();
	l[ll]=r[ll]=0;
	return ll++;
}
void up_(int p)
{
	if(!p)
		return;
	sz[p]=sz[l[p]]+sz[r[p]]+1;
}
void split(int k,int x,int &a,int &b)
{
	if(!k)
	{
		a=b=0;
		return;
	}
	if(v[k]<=x)
	{
		a=k;
		split(r[k],x,r[k],b);
	}
	else
	{
		b=k;
		split(l[k],x,a,l[k]);
	}
	up_(k);
}
int merge(int a,int b)
{
	if(!a||!b)
		return a+b;
	if(w[a]>w[b])
	{
		r[a]=merge(r[a],b);
		up_(a);
		return a;
	}
	else
	{
		l[b]=merge(a,l[b]);
		up_(b);
		return b;
	}
}
void add(int v)
{
	int a,b;
	split(root,v,a,b);
	root=merge(merge(a,New(v)),b);
}
void era(int v)
{
	int a,b,c;
	split(root,v,a,c);
	split(a,v-1,a,b);
	root=merge(merge(a,merge(l[b],r[b])),c);
}
int pre(int vv)
{
	int a,b,re=-2147483647,p;
	split(root,vv-1,a,b);
	p=a;
	while(p)
	{
		re=v[p];
		int t=p;
		p=r[t];
	}
	root=merge(a,b);
	return re;
}
int nxt(int vv)
{
	int a,b,re=2147483647,p;
	split(root,vv,a,b);
	p=b;
	while(p)
	{
		re=v[p];
		p=l[p];
	}
	root=merge(a,b);
	return re;
}
stack<int>st;
int main()
{
	scanf("%d%d",&n,&m);
	char c;
	int x;
	add(0);
	add(n+1);
	for(int i=1;i<=m;i++)
	{
		cin>>c;
		if(c=='D')
		{
			cin>>x;
			st.push(x);
			bj[x]=1;
			add(x);
		}
		else
		if(c=='R')
		{
			era(st.top());
			st.pop();
			bj[x]=0;
		}
		else
		if(c=='Q')
		{
			cin>>x;
			if(!bj[x])
				printf("%d\n",nxt(x)-pre(x)-1);
			else
				printf("0\n");
		}
	}
	return 0;
}