鬼子进村 fhq-treap
观察题目发现可用平衡树做：每次鬼子拆家即从平衡树中加入被拆的节点；每次村民修房子都向平衡树中删除该节点；每次查询时，只需要求出其后驱与前驱，易知nxt-pre-1为答案。
使用\(\text{fhq-treap}\)实现平衡树部分
#include <cstdio>
#include <cstdlib>
#define MAXN 50005
using namespace std;
struct nod{
int sl,sr,val,rnd,sz;
} tre[MAXN];
void update(int x){
tre[x].sz=1+tre[tre[x].sl].sz+tre[tre[x].sr].sz;
}
int merge(int x, int y){
if(x==0||y==0) return x|y;
if(tre[x].rnd<tre[y].rnd){
tre[x].sr=merge(tre[x].sr, y);
update(x);
return x;
}else{
tre[y].sl=merge(x, tre[y].sl);
update(y);
return y;
}
}
void split(int cur, int k, int &x, int &y){
if(cur==0){x=y=0; return;}
if(tre[cur].val<=k){
x=cur;
split(tre[cur].sr, k, tre[cur].sr, y);
}else{
y=cur;
split(tre[cur].sl, k, x, tre[cur].sl);
}
update(cur);
}
int tot,rot,x,y,z;
int new_nod(int val){
tre[++tot].val=val;
tre[tot].sz=1;
tre[tot].rnd=rand();
return tot;
}
void add(int val){
split(rot, val, x, y);
rot=merge(merge(x, new_nod(val)), y);
}
void del(int val){
split(rot, val, x, z);
split(x, val-1, x, y);
y=merge(tre[y].sl, tre[y].sr);
rot=merge(merge(x, y), z);
}
int get_kth(int cur, int k){
while(1){
if(k<=tre[tre[cur].sl].sz) cur=tre[cur].sl;
else if(k==tre[tre[cur].sl].sz+1) return cur;
else k-=tre[tre[cur].sl].sz+1, cur=tre[cur].sr;
}
}
int get_pre(int val){
split(rot, val-1, x, y);
int res=get_kth(x, tre[x].sz);
rot=merge(x,y);
return res;
}
int get_nxt(int val){
split(rot, val, x, y);
int res=get_kth(y, 1);
rot=merge(x,y);
return res;
}
int n,m;
int s[MAXN],top;
bool des[MAXN];
int main(){
srand((unsigned)19270817);
scanf("%d %d", &n, &m);
add(0),add(n+1);
while(m--){
char opt;int t;
scanf("\n%c ", &opt);
if(opt=='D'){
scanf("%d", &t);
add(t);
s[++top]=t;
des[t]=1;
}else if(opt=='Q'){
scanf("%d", &t);
if(des[t]) printf("0\n");
else printf("%d\n", tre[get_nxt(t)].val-tre[get_pre(t)].val-1);
}else if(opt=='R'){
while(des[s[top]]==0) ++top;
des[s[top]]=0;
del(s[top--]);
}else puts("Erro!");
}
return 0;
}