考虑摧毁一个就在treap中加入对应节点，询问时查一下左邻右舍（封死了）减一减。

只AC了前两个点。

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define MAXN 1000010
#define int ll

int ch[MAXN][3], val[MAXN], rnd[MAXN], sz[MAXN], cnt, root, x, y, z;
il void upd(int now) {sz[now] = 1 + sz[ch[now][0]] + sz[ch[now][1]];}
void split(int now, int k, int &x, int &y) {
  if(!now) { x = y = 0; return; }
  else if(val[now] <= k) {
    x = now;
    split(ch[now][1], k, ch[now][1], y);
  }
  else {
    y = now;
    split(ch[now][0], k, x, ch[now][0]);
  }
  upd(now);
}
int merge(int a, int b) {
  if(!a || !b) return a + b;
  if(rnd[a] < rnd[b]) {
    ch[a][1] = merge(ch[a][1], b);
    upd(a);
    return a;
  }
  else {
    ch[b][0] = merge(a, ch[b][0]);
    upd(b);
    return b;
  }
}
int newnode(int a) {
  sz[++cnt] = 1;
  val[cnt] = a;
  rnd[cnt] = rand();
  return cnt;
}
void insert(int a) {
  split(root, a, x, y);
  root = merge(merge(x, newnode(a)), y);
}
void del(int a) {
  split(root, a, x, z);
  split(x, a - 1, x, y);
  y = merge(ch[y][0], ch[y][1]);
  root = merge(merge(x, y), z);
}
int rank(int a) {
  split(root, a - 1, x, y);
  int res = sz[x] + 1;
  root = merge(x, y);
  return res;
}
int kth(int now, int k) {
  while(1) {
    if(k <= sz[ch[now][0]]) now = ch[now][0];
    else if(k == sz[ch[now][0]] + 1) return now;
    else k -= sz[ch[now][0]] + 1, now = ch[now][1];
  }
}
int pre(int a) {
  split(root, a - 1, x, y);
  int res = val[kth(x, sz[x])];
  root = merge(x, y);
  return res;
}
int nxt(int a) {
  split(root, a, x, y);
  int res = val[kth(y, 1)];
  root = merge(x, y);
  return res;
}
int st[MAXN], tot;
bool ok[MAXN];
signed main() {
  srand(19260816);
  int n, T;
  scanf("%d%d\n", &n, &T);
  insert(0), insert(n + 1);
  while(T--) {
    char op;
    int x;
    op = getchar();
    //putchar(op);

    if(op == 'D') {
      scanf("%d\n", &x);
      insert(x);
      st[++tot] = x;
      ok[x] = 1;
    }
    else if(op == 'R') {
      getchar();
      del(st[tot]);
      ok[st[tot]] = 0;
      --tot;
    }
    else {
      scanf("%d\n", &x);
      if(ok[x]) puts("0");
      else print(nxt(x) - pre(x) - 1, '\n');
      //printf("%d\t%d\n", nxt(x), pre(x));
  }
  return 0;
}