提供两种做法，fhq_treap和set
思路：
- 首先在平衡树中加入0节点和n+1节点，是左右边界
- 'D x':在平衡树中加入x节点(为什么是加入而不是删除，我后面会详细讲到)
- 'R':既然是上一个点恢复了，而样例的最后一个询问为我们贴心地考虑了连续恢复的情况，那么就是要维护一个后进先出的
栈来保存您删除的点啦~ - 'Q x'查询x点的前驱pre上一个被删除的点），和x的后继suc下一个被删除的点，那么x能到达的点的个数就是suc-pre-1个（题目给的是一条编号连续的链，那么根据编号来查找个数就很方便啦^ _ ^）
fhq_treap
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
const int N=5e4+10;
int tot,siz[N],val[N],rnd[N],son[N][2];
int x,y,n,rt,m;
inline void upd(int x){siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;}
inline int new_node(int x){siz[++tot]=1;val[tot]=x;rnd[tot]=rand();return tot;}
inline void split(int now,int k,int &x,int &y){
if(!now)x=y=0;
else{
if(val[now]<=k)
x=now,split(son[now][1],k,son[now][1],y);
else
y=now,split(son[now][0],k,x,son[now][0]);
upd(now);
}
}
inline int merge(int x,int y){
if(!x || !y)return x^y;
if(rnd[x]<rnd[y]){
son[x][1]=merge(son[x][1],y);
upd(x);
return x;
}
else{
son[y][0]=merge(x,son[y][0]);
upd(y);
return y;
}
}
int kth(int x,int k){
while(1){
if(siz[son[x][0]]>=k)
x=son[x][0];
else if(siz[son[x][0]]+1==k)
return x;
else
k-=siz[son[x][0]]+1,x=son[x][1];
}
}
int del[N];
stack<int>s;
int main(){
#ifdef WIN32
freopen("guizi.txt","r",stdin);
#endif
srand((unsigned)time(NULL));
rd(n),rd(m);
split(rt,0,x,y);
rt=merge(merge(x,new_node(0)),y);
split(rt,(n+1),x,y);
rt=merge(merge(x,new_node((n+1))),y);
rep(i,1,m){
char op[3];cin>>op;
if(op[0]=='R'){
int z=0;
int last=s.top();
split(rt,last,x,z);
split(x,last-1,x,y);
y=merge(son[y][0],son[y][1]);
rt=merge(merge(x,y),z);
s.pop();
del[last]=0;
}
else if(op[0]=='D'){
int a;rd(a);
split(rt,a,x,y);
rt=merge(merge(x,new_node(a)),y);
s.push(a);
del[a]=1;
}
else if(op[0]=='Q'){
int a;rd(a);
if(del[a]){
puts("0");
continue;
}
split(rt,a-1,x,y);
int pre=val[kth(x,siz[x])];
// printf("%d的前驱为%d
",a,pre);
rt=merge(x,y);
split(rt,a,x,y);
int suc=val[kth(y,1)];
rt=merge(x,y);
// printf("%d的后继为%d
",a,suc);
printf("%d
",suc-pre-1);
}
}
return 0;
}
set
用set真是太太太方便啦
#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,u) for(int i=head[u];i;i=e[i].next)
const int M=5e4+10;
int q[M],tail,n,m;
set<int> s;
set<int>:: iterator it;
stack<int>sta;
int main(){
#ifdef WIN32
freopen("guizi.txt","r",stdin);
#endif
rd(n),rd(m);
s.insert(0);
s.insert(n+1);
while(m--){
char c;cin>>c;
if(c=='D'){
int x;rd(x);
s.insert(x);
sta.push(x);
}
else if(c=='Q'){
int x;rd(x);
it=s.lower_bound(x);
if(*it==x){
puts("0");
continue;
}
printf("%d
",*it-*(--it)-1);
}
else if(c=='R'){
it=s.find(sta.top());
sta.pop();
s.erase(it);
}
}
return 0;
}