题解：
答案=后缀-前缀-1
如果被轰了，那么就时0
在一开始加入0，n+1，保证有前缀后缀
代码：
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int N=100005; char s[3]; int n,m,la[N],ppp,pre[N],in[N],x,size[N],c[N][2],root,tot,data[N]; void rot(int x) { int y=pre[x],k=(c[y][0]==x); size[y]=size[c[y][k]]+size[c[x][k]]+1; size[x]=size[c[x][!k]]+size[y]+1; c[y][!k]=c[x][k]; pre[c[y][!k]]=y; pre[x]=pre[y]; if(pre[y])c[pre[y]][c[pre[y]][1]==y]=x; c[x][k]=y;pre[y]=x; } void splay(int x,int g) { for(int y=pre[x];y!=g;rot(x),y=pre[x]) if(pre[y]!=g)rot((x==c[y][0])==(y==c[pre[y]][0])?y:x); if(g==0)root=x; } void insert(int x) { int y=root; while(c[y][x>data[y]]) y=c[y][x>data[y]]; data[++tot]=x; c[tot][0]=c[tot][1]=0; pre[tot]=y; if(y)c[y][x>data[y]]=tot; splay(tot,0); } void del(int x) { int y=root; while(data[y]!=x) y=c[y][x>data[y]]; splay(y,0); y=c[root][1]; bool b; if(!y) b=1,y=c[root][0];else b=0; while(c[y][b]) y=c[y][b]; splay(y,root); c[y][b]=c[root][b];pre[c[root][b]]=y;pre[y]=0;root=y; size[y]=size[c[y][!b]]+size[c[y][b]]; } int findpre(int x) { int ans; for(int y=root;y;) if(data[y]<x)ans=data[y],y=c[y][1]; else y=c[y][0]; return ans; } int findnxt(int x) { int ans; for(int y=root;y;) if(data[y]<=x)y=c[y][1]; else ans=data[y],y=c[y][0]; return ans; } int read() { int x=0;char c; for (;c<'0'||c>'9';c=getchar()); for (;c>='0'&&c<='9';c=getchar())x=x*10+c-48; return x; } void write(int x) { if (x>=10)write(x/10); putchar(x%10+48); } int main() { n=read();m=read(); insert(0);insert(n+1); while (m--) { scanf("%s",&s); if (s[0]=='D') { x=read(); insert(x); in[x]=1; la[++ppp]=x; } if (s[0]=='Q') { x=read(); if (in[x]) { puts("0"); continue; } int l=findpre(x),r=findnxt(x); write(r-l-1);puts(""); } if (s[0]=='R'&&ppp)in[la[ppp]]=0,del(la[ppp--]); } }