土罐的序列题解¶

解法署名：维护段数的隐式伸展树来自出题人解法；Codex（GPT-6）负责区间定位、标记下传的实现与段数合并证明。

解法比较¶

出题人解法使用按位置维护的伸展树，并在首尾放置两个哨兵。每个子树保存大小、首尾类型和连续同类段数，合并时扣掉连接处相同类型造成的重复段。整段赋值把段数改为一；翻转交换左右孩子和首尾类型，段数不变。两种操作均使用延迟标记。

赋值、翻转和查询都通过两次伸展隔离目标区间。移动先取出对应子树，再在剩余序列中按排名寻找插入空隙，将子树挂回并伸展。排名使用取出后的序列，移动位置由剩余序列中的排名确定。中序顺序、段数合并与标记的不变量及证明见下文，适用于两份实现。

两者均线性初始化，每次操作进行常数次伸展、分离或连接；总时间为摊还 \(O(n+m\log(n+1))\) ，空间为 \(O(n)\) .

Codex 实现把插入空隙也交给两边界隔离过程处理，使区间操作和移动共用同一套定位方式；在伸展函数内部显式收集祖先并下传标记，减少对调用者预先下传的依赖。节点关系改用数组下标，补齐段数合并证明与边界说明。

区间操作与移动共用边界定位过程，伸展函数集中负责祖先标记下传；这些实现选择便于维护同一组不变量，不改变渐进复杂度。

对一段序列维护长度、首类型、尾类型和段数。连接两个非空序列 \(A,B\) 时，只有连接处可能合并两段，因此

\[ \operatorname{runs}(AB)=\operatorname{runs}(A)+\operatorname{runs}(B)-[\operatorname{last}(A)=\operatorname{first}(B)] \]

空序列贡献零段；不能拿空序列的哨兵值参与相等判断。将左子树、当前元素、右子树依次合并，就能维护整棵辅助子树的统计量。

整段赋值为 \(v\) 后，首尾类型都为 \(v\) ，段数变为 \(1\) ，长度不变。

整段翻转后，段数不变，交换首尾类型，并交换左右孩子。赋值标记记录尚未传给孩子的新类型；翻转标记记录尚未下传的顺序反转。两种操作作用于类型和顺序，可以同时保存。下传时先赋值再翻转，与参考程序的表示方式一致。

每次按大小寻找位置或旋转前，都必须下传相关祖先的标记。否则节点大小对应的顺序或边界类型可能过期。

加入首尾两个不会被操作的哨兵。按中序位置维护伸展树，利用子树大小查找排名。

要隔离 \([l,r]\) ，把其前一个元素伸展到根，再把其后一个元素伸展到根的右孩子。右孩子的左子树就恰好是目标区间。赋值、翻转和查询直接操作这棵子树，再更新两层祖先。

移动时先隔离并断开长度为 \(\mathrm{len}\) 的子树。此时整棵树只包含剩余序列和两个哨兵。在这棵缩短后的树中，隔离第 \(\mathrm{nl}-1\) 个剩余元素之后的空隙，把取出的子树接进去。内部顺序保持不变，且正好占据题目指定的新位置。

取出整个序列后仍有两个哨兵，因此空隙操作也有定义。单个元素、插在首尾和搬回原位置均不需另造规则。

中序序列始终等于当前罐子序列；区间隔离只改变树形，不改变中序顺序。区间更新按定义改变类型或顺序，移动按取出后的下标接回整段，且统计量由连接公式保持正确。因此每次查询都返回恰当段数。

初始化用平衡形状线性建树。每次操作进行常数次伸展、分离或连接，总时间为 \(O(n+m\log(n+1))\) ，为摊还界，空间为 \(O(n)\) .初始化递归只有 \(O(\log(n+1))\) 层；操作阶段的祖先下传用显式栈。

伸展树的摊还分析见 Sleator 和 Tarjan 的 Self-Adjusting Binary Search Trees。这里的段数统计和延迟标记只增加每个被访问节点的常数工作。

独立模型用数组切片逐次执行四种操作，再直接数相邻不同类型的数量。覆盖整列移动、连续翻转、赋值后移动、单点、相同类型边界和插入末尾。