众所周知 Fhq Treap 是 fhq 神仙研究出来的平衡树…

具体实现

每个点实现一个 \(\text{rnd}\) 表示 rand 的值 为什么要 rand 呢

是为了保证树高为 \(\log n\) 从而保证复杂度…

FHQ Treap的核心操作是split和merge，其他的操作均以这两个操作为基础进行。

下面所述操作的数据如下所示：

int rt = 0 , cnt = 0 , a[N] , sz[N] , rnd[N] , ch[N][2] ;

#define ls(x) ch[x][0]

#define rs(x) ch[x][1]

ls 指的是左儿子 rs 指的是右儿子…

val表示节点的权值 用来维护二叉搜索树的性质，rnk表示节点的权值 用来维护堆的性质。

sz 表示节点大小（包括自身）

split

split 实现的操作大概是 把一棵树分成俩…然后左边的值小于等于 \(k\) 右边的值大于 \(k\)

如果你 split(rt , k , x , y)

那么你就把 rt 分成两个部分 \(x\) ，\(y\) 了 其中 \(x\) 的子树的 \(val \leq k\) ， \(y\) 的子树的 \(val > k\)

void split (int cur , int k , int & u , int & v) {

    if(! cur) { u = v = 0 ; return ; }

    if(a[cur] <= k) { u = cur ; split(rs(u) , k , rs(u) , v) ; }

    else { v = cur ; split(ls(v) , k , u , ls(v)) ; }

    pushup(cur) ;

  }

代码如上 如果小于这个则分给左子树 大于就分给右边……

merge

merge的操作就是合并一下根节点和新建节点 然后保留根/替换根（rnd决定）

反正是随机合并 期望树高 \(\log n\)

int merge (int u , int v) {

    if(! u || ! v) return u | v ;

    if(rnd[u] < rnd[v]) { rs(u) = merge(rs(u) , v) ; pushup(u) ; return u ; }

    else { ls(v) = merge(u , ls(v)) ; pushup(v) ; return v ; }

  }

kth

Treap 都满足一个堆的性质… 所以显然…

可以按照 sz 来找 kth 递归/非递归都可以啊…

int kth(int u , int k) {

    if(k <= sz[ls(u)]) return kth(ls(u) , k) ;

    if(sz[ls(u)] + 1 == k) return a[u] ;

    return kth(rs(u) , k - sz[ls(u)] - 1) ;

  }

递归写法

rank

rank的话就分离一个 \(val = k-1\) 的子树…然后求这个子树的 sz 就知道 rank 了啊

  int rank(int k) {

    int x , y , res ; split(rt , k - 1 , x , y) ;

    res = sz[x] + 1 ; rt = merge(x , y) ; return res ;

  }

其他操作不讲了

#include <cstdio>

#include <cstdlib>

using ll = long long ;

using namespace std ;

int read() {

  int x = 0 , f = 1 ; char c = getchar() ;

  while(c < '0' || c > '9') { if(c == '-') f = -1 ; c = getchar() ; }

  while(c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c & 15) ; c = getchar() ; }

  return x * f ;

}

template < class T > void print(T x , char c = '\n') {

  static char _st[100] ; int _stp = 0 ;

  if(x == 0) { putchar('0') ; }

  if(x < 0) { putchar('-') ; x = -x ; }

  while(x) { _st[++ _stp] = (x % 10) ^ 48 ; x /= 10 ; }

  while(_stp) { putchar(_st[_stp --]) ; }

  putchar(c) ;

}

int q ;

const int N = 1e5 + 10 ;

class Fhq {

public:

  int rt = 0 , cnt = 0 , a[N] , sz[N] , rnd[N] , ch[N][2] ;

#define ls(x) ch[x][0]

#define rs(x) ch[x][1]

  int newNode (int x) { sz[++ cnt] = 1 ; a[cnt] = x ; rnd[cnt] = rand() ; return cnt ; }

  void pushup (int u) { sz[u] = sz[ls(u)] + sz[rs(u)] + 1 ; }

  int merge (int u , int v) {

    if(! u || ! v) return u | v ;

    if(rnd[u] < rnd[v]) { rs(u) = merge(rs(u) , v) ; pushup(u) ; return u ; }

    else { ls(v) = merge(u , ls(v)) ; pushup(v) ; return v ; }

  }

  void split (int cur , int k , int & u , int & v) {

    if(! cur) { u = v = 0 ; return ; }

    if(a[cur] <= k) { u = cur ; split(rs(u) , k , rs(u) , v) ; }

    else { v = cur ; split(ls(v) , k , u , ls(v)) ; }

    pushup(cur) ;

  }

  void insert(int k) {

    int x , y ; split(rt , k , x , y) ; rt = merge(merge(x , newNode(k)) , y) ;

  }

  void erase(int k) {

    int x , y , z ; split(rt , k , x , z) ; split(x , k - 1 , x , y) ;

    y = merge(ls(y) , rs(y)) ; rt = merge(merge(x , y) , z) ;

  }

  int kth(int u , int k) {

    if(k <= sz[ls(u)]) return kth(ls(u) , k) ;

    if(sz[ls(u)] + 1 == k) return a[u] ;

    return kth(rs(u) , k - sz[ls(u)] - 1) ;

  }

  int rank(int k) {

    int x , y , res ; split(rt , k - 1 , x , y) ;

    res = sz[x] + 1 ; rt = merge(x , y) ; return res ;

  }

  int pre(int k) {

    int x , y , res ; split(rt , k - 1 , x , y) ;

    res = kth(x , sz[x]) ; rt = merge(x , y) ; return res ;

  }

  int suf(int k) {

    int x , y , res ; split(rt , k , x , y) ;

    res = kth(y , 1) ; rt = merge(x , y) ; return res ;

  }

} T ;

int main() {

  srand(19260817) ;

  q = read() ;

  while(q --) {

    int opt = read() , x = read() ;

    if(opt == 1) { T.insert(x) ; }

    if(opt == 2) { T.erase(x) ; }

    if(opt == 3) { print(T.rank(x)) ; }

    if(opt == 4) { print(T.kth(T.rt , x)) ; }

    if(opt == 5) { print(T.pre(x)) ; }

    if(opt == 6) { print(T.suf(x)) ; }

  }

  return 0 ;

}

同样的 fhq 不仅仅是可以用来按 \(val\) 分离 还可以用 \(size\) 分离成两棵树 (文艺平衡树代码)

#include <cstdio>

#include <cstdlib>

using ll = long long ;

using namespace std ;

int read() {

  int x = 0 , f = 1 ; char c = getchar() ;

  while(c < '0' || c > '9') { if(c == '-') f = -1 ; c = getchar() ; }

  while(c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c & 15) ; c = getchar() ; }

  return x * f ;

}

template < class T > void print(T x , char c = '\n') {

  static char _st[100] ; int _stp = 0 ;

  if(x == 0) { putchar('0') ; }

  if(x < 0) { putchar('-') ; x = -x ; }

  while(x) { _st[++ _stp] = (x % 10) ^ 48 ; x /= 10 ; }

  while(_stp) { putchar(_st[_stp --]) ; }

  putchar(c) ;

}

int n , q ;

const int N = 1e5 + 10 ;

class Fhq {

public:

  int ch[N][2] , rnd[N] , a[N] , sz[N] , rt = 0 , cnt = 0 ;

  bool rev[N] ;

#define ls(x) ch[x][0]

#define rs(x) ch[x][1]

  void pushup(int u) { sz[u] = sz[ls(u)] + sz[rs(u)] + 1 ; }

  void swap(int & x , int & y) { x ^= y ^= x ^= y ; }

  void pushr(int u) { swap(ls(u) , rs(u)) ; rev[u] ^= 1 ; }

  void pushdown(int u) {

    if(! rev[u]) return ;

    if(ls(u)) pushr(ls(u)) ;

    if(rs(u)) pushr(rs(u)) ;

    rev[u] ^= 1 ;

  }

  int merge(int x , int y) {

    if(! x || ! y) return x | y ;

    if(rnd[x] < rnd[y]) {

      pushdown(x) ;

      rs(x) = merge(rs(x) , y) ;

      pushup(x) ;

      return x ;

    }

    pushdown(y) ;

    ls(y) = merge(x , ls(y)) ;

    pushup(y) ;

    return y ;

  }

  void split(int cur , int k , int & u , int & v) {

    if(! cur) { u = v = 0 ; return ; }

    pushdown(cur) ;

    if(sz[ls(cur)] < k) {

      u = cur ;

      split(rs(u) , k - sz[ls(cur)] - 1 ,rs(u) , v) ;

    }

    else {

      v = cur ;

      split(ls(v) , k , u , ls(v)) ;

    }

    pushup(cur) ;

  }

  void reverse(int l , int r) {

    int x , y , z ; x = y = z = 0 ;

    split(rt , l - 1 , x , y) ;

    split(y , r - l + 1 , y , z) ;

    pushr(y) ;

    rt = merge(merge(x , y) , z) ;

  }

  int newNode(int x) { sz[++ cnt] = 1 ; a[cnt] = x ; rnd[cnt] = rand() ; return cnt ; }

  void push_back(int x) { rt = merge(rt , newNode(x)) ; }

  void dfs(int u) {

    pushdown(u) ;

    if(ls(u)) dfs(ls(u)) ;

    print(a[u] , ' ') ;

    if(rs(u)) dfs(rs(u)) ;

  }

} T ;

int main() {

  srand(19260817) ;

  n = read() ; q = read() ;

  for(int i = 1 ; i <= n ; i ++) T.push_back(i) ;

  while(q --) {

    int l = read() , r = read() ;

    T.reverse(l , r) ;

  }

  T.dfs(T.rt) ;

  return 0 ;

}

自行理解 我顺便解释一下子 fhq是一种按中序遍历建树的玩意 所以如果需要输出就直接按中序遍历输出了 ovo

如果有没看懂的欢迎评论 quq