Treap

#include "../../header.cpp"
mt19937_64 MT(114514);
namespace Treap{
  const int SIZ = 1e6 + 1e5 + 3;
  int F[SIZ], C[SIZ], S[SIZ], W[SIZ], X[SIZ][2], sz;
  u64 H[SIZ];
  bool is_root(int x){ return   F[x]   == 0;}
  bool is_rson(int x){ return X[F[x]][1] == x;}
  int  newnode(int w){
    W[++ sz] = w, C[sz] = S[sz] = 1; H[sz] = MT();
    return sz;
  }
  void pushup(int x){
    S[x] = C[x] + S[X[x][0]] + S[X[x][1]];
  }
  void rotate(int &root, int x){
    int y = F[x], z = F[y];
    bool f = is_rson(x);
    bool g = is_rson(y);
    int &t = X[x][!f];
    if(z){ X[z][g] = x; } else root = x;
    if(t){ F[t]  = y; }
    X[y][f] = t, t = y;
    F[y] = x, pushup(y);
    F[x] = z, pushup(x);
  }
  void insert(int &root, int w){
    if(root == 0) {root = newnode(w); return;}
    int x = root, o = x;
    for(;x;o = x, x = X[x][w > W[x]]){
      ++ S[x]; if(w == W[x]){ ++ C[x], o = x; break;}
    }
    if(W[o] != w){
      if(w < W[o]) X[o][0] = newnode(w), F[sz] = o, o = sz;
      else     X[o][1] = newnode(w), F[sz] = o, o = sz;
    }
    while(!is_root(o) && H[o] < H[F[o]])
      rotate(root, o);
  }
  void erase(int &root, int w){
    int x = root, o = x;
    for(;x;o = x, x = X[x][w > W[x]]){
      -- S[x]; if(w == W[x]){ -- C[x], o = x; break;}
    }
    if(C[o] == 0){
      while(X[o][0] || X[o][1]){
        u64 wl = X[o][0] ? H[X[o][0]] : ULLONG_MAX;
        u64 wr = X[o][1] ? H[X[o][1]] : ULLONG_MAX;
        if(wl < wr){
          int p = X[o][0]; rotate(root, p);
        } else {
          int p = X[o][1]; rotate(root, p);
        }
      }
      if(is_root(o)){
        root = 0;
      } else {
        X[F[o]][is_rson(o)] = 0;
      }
    }
  }
  int  find_rank(int &root, int w){
    int x = root, o = x, a = 0;
    for(;x;){
      if(w <  W[x])
        o = x, x = X[x][0];
      else {
        a += S[X[x][0]];
        if(w == W[x]){
          o = x; break;
        }
        a += C[x];
        o = x, x = X[x][1];
      }
    }
    return a + 1;
  }
  int  find_kth(int &root, int w){
    int x = root, o = x, a = 0;
    for(;x;){
      if(w <= S[X[x][0]])
        o = x, x = X[x][0];
      else {
        w -= S[X[x][0]];
        if(w <= C[x]){
          o = x; break;
        }
        w -= C[x];
        o = x, x = X[x][1];
      } 
    }
    return W[x];
  }
  int  find_pre(int &root, int w){
    return find_kth(root, find_rank(root, w) - 1);
  }
  int  find_suc(int &root, int w){
    return find_kth(root, find_rank(root, w + 1));
  }
}