# FHQ Treap：按值分裂、合并与顺序统计

## 本节目标

掌握无旋 Treap（FHQ Treap）的两条原语 `split/merge`，维护动态有序多重集的插入、删除、第 k 小、排名及极值删除。

## 前置知识与课前自测

前置：BST、随机化、子树大小。

1. `split(root,key)` 应保证两棵树满足什么键范围？
2. `merge(a,b)` 需要什么前置条件？
3. 为什么随机优先级能给出期望对数树高？

<details><summary>答案</summary>

1. 左树键不大于 key，右树键大于 key（或另一套统一约定）。
2. a 的所有键不大于 b 的所有键。
3. 键确定 BST 中序，独立随机优先级确定笛卡尔树；其期望深度与随机 BST 同阶。

</details>

## 问题动机与核心知识

FHQ Treap 不围绕某节点旋转，而是把所有操作归结为：

- 按键/排名切成两棵合法 Treap；
- 在键域有序前提下，按随机优先级合并。

节点同时满足键的 BST 顺序和随机优先级的堆顺序。`size` 在每次改儿子后 `pull`。重复值可每次建独立节点，也可存 `count`；附件前者更统一。

## 实现指南

- 随机数使用固定高质量生成器，避免 `rand()` 低位和对抗数据。
- 删除一个值时切成 `<x`、`==x`、`>x`，只删等值树一个节点。
- 递归期望深度对数，但随机性失效仍可能退化；这也是它与保证最坏界结构的差别。
- `kth` 前确认 $1\le k\le size(root)$。

## 精选例题 1：Black Box

### 来源与题意

- [POJ-1442 Black Box](https://vjudge.net/problem/POJ-1442)，Northeastern Europe 1996
- 依次插入给定序列；第 i 次询问发生在已插入前 $u_i$ 个数后，输出当前第 i 小。

<details><summary>Hint 1</summary>询问位置单调，继续插入到 $u_i$ 即可。</details>
<details><summary>Hint 2</summary>Treap 的子树大小支持第 k 小。</details>

### Observations、Editorial 与证明

时间轴只前进、不删除，所以在每次询问前补插新元素，然后沿 `left_size` 选择第 i 小。Treap 中序序列始终是当前多重集排序结果；`kth` 根据左子树元素数排除整棵子树，归纳能到达排序序列第 k 项。期望复杂度 $O((M+N)\log M)$。

### 核心伪代码与附件

```text
for query_index i in 1..Q:
    while inserted < u[i]: root = insert(root, next_value)
    output kth(root, i)
```

[完整 C++17 附件](../../参考实现/11-平衡树/POJ-1442.cpp)

## 精选例题 2：Double Queue

### 来源与题意

- [POJ-3481 Double Queue](https://vjudge.net/problem/POJ-3481)，Southeastern Europe 2007
- 动态加入 `(客户编号,优先级)`，支持弹出最高优先级或最低优先级客户；空时输出 0。

<details><summary>Hint 1</summary>以优先级为 BST 键，节点附带客户编号。</details>
<details><summary>Hint 2</summary>最小/最大分别是最左/最右节点，输出后按键删除。</details>

### Observations

- 队列名称不重要，操作集合决定它是有序集合。
- 极值查询可沿单链完成，不需维护额外 min/max。
- 删除后必须重新合并被切开的左右树，保持所有权唯一。

### Editorial 与正确性证明

插入时按优先级分裂并夹入新节点。删除极值先找到键，再把 `<key`、`==key`、`>key` 分开，丢弃等值根并合并其子树后接回。分裂/合并保持中序键序与优先级堆序，所以每步后仍是合法 Treap；中序极端节点正是优先级极值。每操作期望 $O(\log n)$。

### 核心伪代码与附件

```text
insert(id, priority): split by priority; merge(left, new_node, right)
pop_min/max:
    find extreme node by left/right pointers
    output its id
    erase one node with that priority via splits and merges
```

[完整 C++17 附件](../../参考实现/11-平衡树/POJ-3481.cpp)

## 扩展与联系

FHQ Treap 可按键持久化：split/merge 时路径复制；也可按排名成为隐式序列树，见下一节。若要求严格最坏 $O(\log n)$，需红黑树、AVL 等确定性结构。

## 总结与自检

1. split 与 merge 的前后条件是什么？
2. 重复值删除一个时如何切分？
3. kth 怎样利用左子树大小？
4. 随机优先级影响正确性还是只影响复杂度？

## 课后训练建议

与 `multiset` 随机对拍插删、排名、kth。主动插入递增键检查树高分布；固定随机种子便于复现失败。