Treap

讲是 Treap，实际上只有 FHQ Treap 会用到。FHQ Treap 就是非旋 Treap。

一、定义

定义一个树为 Treap 当且仅当每个节点的 $key$（关键字）满足二叉搜索树的性质（中序遍历是有序的），且 $pri$（优先级）满足小根堆的性质（父亲永远比孩子小）。

二、操作

讲白了就两种，一个分裂一个合并。

1. 合并
   现在有一个 Treap L 和一个 Treap R，L 中所有元素 $key$ 比 R 小。
   我们考虑跟左偏树一样的合并，就是每次不是 l = merge(l, r.ls) 就是 r = merge(l.rs, r)。
   考虑这样进行合并。下图中以粗体表示 $key$，斜体表示 $pri$。

       flowchart TD
    classDef red stroke:red
    classDef cyan stroke:cyan
    classDef empty fill:transparent,stroke:transparent,color:transparent
    subgraph BEF1[ ]
        direction TB
        A1("4 1") --> B1("2 6") --> C1("1 7")
        B1 --> D1("3 10")
        A1 --> E1("5 4")
        A1:::red;B1:::red;C1:::red;D1:::red;E1:::red;
    end
    subgraph BEF2[ ]
        direction TB
        A2("7 2") --> B2("6 9")
        A2 --> C2("9 3")
        C2 --> D2("8 5")
        C2 --> E2("10 8")
        A2:::cyan;B2:::cyan;C2:::cyan;D2:::cyan;E2:::cyan;
    end
    subgraph AFT[ ]
        direction TB
        A3("4 1") --> B3("2 6") --> C3("1 7")
        B3 --> D3("3 10")
        A3 --> A4("7 2") --> E3("5 4") --> e:::empty
        E3 --> B4("6 9")
        A4 --> C4("9 3")
        C4 --> D4("8 5")
        C4 --> E4("10 8")
        A3:::red;B3:::red;C3:::red;D3:::red;E3:::red;
        A4:::cyan;B4:::cyan;C4:::cyan;D4:::cyan;E4:::cyan;
    end
    subgraph BEF[ ]
        direction LR
        BEF1---BEF2
    end
    BEF <--> AFT
    linkStyle 13 fill:transparent,stroke:transparent

   注意到我们既保持了 $key$ 又保持了 $pri$。

2. 分裂
   考虑我们将一个树中序遍历出来的序列分成两个部分，也就是逆向刚刚的操作。
   可以使用树上二分递归地去做。如果当前根就是左部分的最后一个，那就直接断成 $(u,u.r)$。否则根据当前的 $key$ 判断是要往左孩子递归还是右孩子递归。将得到的分割 $(l,r)$ 再做相应的合并即可。

   注意这里有一个变种，就是如果我们选择根据序列下标（也就是中序遍历之后给一个下标分裂成 $[l,p]$ 和 $[p+1,r]$）。这种变种其实是将左子树的节点数量 $+ 1$ 作为 $key$，维护是一样的。

三、实现

1. 节点信息

   struct Node {
       decltype(rng()) prio;
       int ls, rs, val, sum, sz, cov, add, refCnt;
       bool rev;
       inline Node(int x = 0) : prio(rng()), ls(), rs(), val(x), sum(x), sz(1), cov(-1), add(), refCnt(1), rev() {}
       inline void cover(int x) { if (~x) add = 0, val = cov = x, sum = 1ull * x * sz % MOD; }
       inline void plus(int x) { if (x) Add(add, x), Add(val, x), Add(sum, 1ull * x * sz % MOD); }
       inline void flip() { std::swap(ls, rs); rev ^= 1; }
   } tr[N << 3];
   inline void pushup(int u) {
       U.sz = UL.sz + 1 + UR.sz;
       Add(U.sum = U.val, UL.sum), Add(U.sum, UR.sum);
   }
   inline void pushdown(int u) {
       if (U.ls) { clone(U.ls); if (U.rev) UL.flip(); UL.cover(U.cov), UL.plus(U.add); }
       if (U.rs) { clone(U.rs); if (U.rev) UR.flip(); UR.cover(U.cov), UR.plus(U.add); }
       U.cov = -1, U.add = 0, U.rev = false;
   }

2. 分割合并

       std::pair<int,int> splitByOrd(int u, int ord) {
       if (!u) return {0,0};
       clone(u); pushdown(u);
       if (UL.sz + 1 == ord) {
           auto rs = U.rs;
           U.rs = 0; pushup(u);
           return {u, rs};
       }
       if (UL.sz < ord) {
           auto [ls, rs] = splitByOrd(U.rs, ord - UL.sz - 1);
           U.rs = ls; pushup(u);
           return {u, rs};
       }
       auto [ls, rs] = splitByOrd(U.ls, ord);
       U.ls = rs; pushup(u);
       return {ls, u};
   }
   int merge(int l, int r) {
       if (!l || !r) return l | r;
       clone(l); pushdown(l);
       clone(r); pushdown(r);
       if (1ull * tr[l].sz * rng() < 1ull * tr[r].sz * rng()) {
           tr[l].rs = merge(tr[l].rs, r);
           return pushup(l), l;
       }
       tr[r].ls = merge(l, tr[r].ls);
       return pushup(r), r;
   }

注意到这里面有一个神秘函数 clone，其实他是用来可持久化的。因为 Splay 挺好写的而且又快，所以一般不用 Treap。所以其优势在于可持久化。
写的时候注意如果更改节点信息就复制一份就可以了。

3. 应用示例

   inline int querySum(int l, int r) {
       // 这里相当于是查询 key 在 [l+1,r+1] 的序列统计信息，这样写是因为我前后放了哨兵
       auto [mid, rs] = splitByOrd(rt, ++r);
       auto [ls, u] = splitByOrd(mid, l);
       auto res = U.sum;
       rt = merge(merge(ls, u), rs);
       return res;
   }
   void extract(std::vector<int>& arr, int u = rt) { // 中序遍历出序列
       if (!u) return;
       pushdown(u);
       extract(arr, U.ls);
       arr.push_back(U.val);
       extract(arr, U.rs);
   }