旋转treap

const int maxn=2e5+5;//treap中最多几个节点

struct {
  int l[maxn], r[maxn], val[maxn], rnd[maxn], size_[maxn], w[maxn];
  int sz, ans, rt;

  void pushup(int x) { size_[x] = size_[l[x]] + size_[r[x]] + w[x]; }//必写

  void lrotate(int &k) {//必写
    int t = r[k];
    r[k] = l[t];
    l[t] = k;
    size_[t] = size_[k];
    pushup(k);
    k = t;
  }

  void rrotate(int &k) {//必写，下面功能为选写
    int t = l[k];
    l[k] = r[t];
    r[t] = k;
    size_[t] = size_[k];
    pushup(k);
    k = t;
  }

  void insert(int &k, int x) {  // 插入, 调用时 T.insert(T.rt,x)  x为要插入的值
    if (!k) {                                      //T.rt为固定格式，下面的k都是T.rt
      sz++;
      k = sz;
      size_[k] = 1;
      w[k] = 1;
      val[k] = x;
      rnd[k] = rand();
      return;
    }
    size_[k]++;
    if (val[k] == x) {
      w[k]++;
    } else if (val[k] < x) {
      insert(r[k], x);
      if (rnd[r[k]] < rnd[k]) lrotate(k);
    } else {
      insert(l[k], x);
      if (rnd[l[k]] < rnd[k]) rrotate(k);
    }
  }

  bool del(int &k, int x) {  // 删除节点， T.del(T.rt,x)  要删除的值（多个相同只会删一个）
    if (!k) return false;
    if (val[k] == x) {
      if (w[k] > 1) {
        w[k]--;
        size_[k]--;
        return true;
      }
      if (l[k] == 0 || r[k] == 0) {
        k = l[k] + r[k];
        return true;
      } else if (rnd[l[k]] < rnd[r[k]]) {
        rrotate(k);
        return del(k, x);
      } else {
        lrotate(k);
        return del(k, x);
      }
    } else if (val[k] < x) {
      bool succ = del(r[k], x);
      if (succ) size_[k]--;
      return succ;
    } else {
      bool succ = del(l[k], x);
      if (succ) size_[k]--;
      return succ;
    }
  }

  int queryrank(int k, int x) {//queryrank(T.rt,x)  值x，在treap中的排名（从小到大）
    if (!k) return 0;        //多个x会输出最小的排名
    if (val[k] == x)         //注：如果题目不保证值x在treap中存在，先 insert(x),再查询rank
      return size_[l[k]] + 1;                                       //最后del(x)才行
    else if (x > val[k]) {
      return size_[l[k]] + w[k] + queryrank(r[k], x);
    } else
      return queryrank(l[k], x);
  }

  int querynum(int k, int x) {//query(T.rt,x)  treap中从小到大排名为x的值是多少，即第x小的数
    if (!k) return 0;                     //如果要转换为第x大就反向算一下排名
    if (x <= size_[l[k]])
      return querynum(l[k], x);
    else if (x > size_[l[k]] + w[k])
      return querynum(r[k], x - size_[l[k]] - w[k]);
    else
      return val[k];
  }

  void querypre(int k, int x) {//值x的前驱，小于x且最大
    if (!k) return;            //调用步骤: 1. T.ans=0	2. T.querypre 	3.cout<<T.val[T.ans]
    if (val[k] < x)
      ans = k, querypre(r[k], x);
    else
      querypre(l[k], x);
  }

  void querysub(int k, int x) {//值x的后继，大于x且最小
    if (!k) return;
    if (val[k] > x)
      ans = k, querysub(l[k], x);
    else
      querysub(r[k], x);
  }
} T;

srand(time(nullptr)) //每个测试点都srand一次