02-隐式FHQ-Treap序列操作.md 4.5 KB
隐式 FHQ Treap：按排名分裂、区间翻转与剪贴
若“值”和“位置”还容易混，先完成 课前零食：把一段话翻过来。它用同一段文字分别预演隐式下标、双哨兵和翻转 Lazy；本节换成 FHQ 的 split/merge 接口。
本节目标
把中序位置而非键作为顺序，使用子树大小按前 k 项分裂；维护翻转 Lazy，并完成区间反转、剪切和拼接。
前置知识与课前自测
前置：上一节 FHQ Treap、Lazy 标记。
- 隐式 Treap 是否还需要
key满足 BST 顺序？ split(root,k)返回的两树各含多少序列元素？- 翻转一棵子树要交换什么，并给孩子传什么标记？
答案
1. 不需要；中序顺序就是序列，排名由 size 隐式决定。 2. 左树前 k 项，右树其余项。 3. 交换左右儿子并 XOR `rev`；下传时对子树应用同操作。问题动机与核心知识
数组插删中段会搬移 $O(n)$ 个元素。隐式 Treap 的中序遍历代表序列，split 按左子树大小决定一个节点属于前 k 项还是后缀。任意区间 $[l,r]$ 可两次 split 暴露成独立根：
prefix_and_mid, suffix = split(root, r)
prefix, mid = split(prefix_and_mid, l-1)
对 mid 打标记，再按原顺序 merge 回去。
实现指南
- split/merge 进入节点前先 push Lazy，否则逻辑位置与儿子指针不一致。
- 翻转标记用 XOR 复合，两次翻转抵消。
- 剪切后插入位置的定义要看题面是基于删除前还是删除后序列。
- 输出用一次中序遍历，避免逐点 kth 产生 $O(n\log n)$。
精选例题 1：Substring Reversals
来源与题意
- CSES-2073 Substring Reversals
- 维护字符串，多次翻转子串，输出最终字符串。
Hint 1
两次按排名 split 取出子串根。Hint 2
对子串根应用 rev，三段 merge 回去。Observations、Editorial 与证明
区间翻转不会改变区间外元素，也不会改变区间元素集合；独立子树的中序翻转恰由交换每个节点左右儿子实现。Lazy 在访问前下传，保证任何时刻从逻辑上读取的中序序列等于所有待执行翻转后的真实序列。每次两次 split、两次 merge，期望 $O(\log n)$。
核心伪代码与附件
left_mid, right = split(root, r)
left, mid = split(left_mid, l-1)
apply_reverse(mid)
root = merge(merge(left, mid), right)
精选例题 2：Cut and Paste
来源与题意
- CSES-2072 Cut and Paste
- 每次剪下字符串区间 $[a,b]$ 并粘到末尾，输出最终串。
Hint 1
分出 `prefix, cut, suffix`。Hint 2
新顺序是 `prefix + suffix + cut`。Observations
- “剪切”只是改变三段根的合并次序，节点无需复制或逐字符移动。
- 被剪段内部顺序保持，因此不打 rev。
- 每个节点仍只属于一个根，合并所有权清楚。
Editorial 与正确性证明
两次 split 按原序列排名得到三段，按题意顺序重新 merge。split 保持每段中序相对顺序，merge 在所有左段元素应位于右段之前的前提下保持各自内部顺序，所以新中序序列精确等于剪贴结果。每次期望 $O(\log n)$。
核心伪代码与附件
left_cut, suffix = split(root, b)
prefix, cut = split(left_cut, a-1)
root = merge(merge(prefix, suffix), cut)
扩展与联系
节点再维护 sum/min，区间根暴露后即可查询；仿射、加法等 Lazy 需按普通线段树原则定义作用和复合。可持久化隐式 Treap 要路径复制，破坏式 merge 不能共享旧根。
总结与自检
- 隐式 Treap 的“键”在哪里？
- 为什么 split 前必须 push？
- 区间翻转的标记怎样复合？
- 剪贴题为什么只改 merge 顺序？
课后训练建议
与 std::string 的 reverse/erase/insert 对拍。每次操作后同时检查中序长度与原长度相等，优先捕捉丢根或重复合并。