# 机器人指令平台：隐式 Treap

Codex（GPT-6）：应用已有的隐式 Treap 数据结构，以序列排名表示环中位置，给出对应程序与证明。

程序：[alternative.cpp](alternative.cpp)。本方案与[双向循环链表](solution.zh.md)并列，支持完整数据。

## 将环表示为序列

任取一个环的切口，按方向 $0$ 把有效节点排成线性序列，用零起始排名 $q$ 标记当前节点。隐式 Treap 的中序序列就是该线性序列；每个节点存子树大小，因此可按排名分裂、合并和查询。切口不影响环的含义。

- 插入：在前 $q+1$ 项后插入新编号；非空环中 $q$ 不变。空环插入后 $q=0$ .
- 删除：分裂出排名为 $q$ 的一个节点并丢弃，将两侧合并。若新大小为 $s'>0$ ，令 $q\gets q\bmod s'$ ；这恰是被删节点的方向 $0$ 后继。空环令 $q=0$ .
- 移动：方向 $0$ 令 $q\gets(q+x)\bmod s$ ，方向 $1$ 令 $q\gets(q-x)\bmod s$ ，最后调整为非负余数；空环跳过。
- 查询：按左子树大小寻找排名 $q$ 对应的编号；空树返回 `-1` .

## 正确性

初始中序序列为 $1,2,\ldots,n$ ，当前排名为零。按排名分裂与合并保持相对次序，所以插入和删除精确对应环中的相邻关系。删除线性末尾时排名回到零，正好实现跨越切口。移动的模运算实现环绕，查找返回当前排名对应的节点。以此归纳，每个操作后的序列和当前位置均与题意相同。

## 复杂度与适用条件

令 $M=n+m$ . 在独立随机优先级的通常分析模型下，树高期望为 $O(\log M)$ ；逐次合并建树期望 $O(n\log M)$ ，插入、删除、查询期望 $O(\log M)$ ，移动为 $O(1)$ . 总时间期望 $O(M\log M)$ ，节点数组空间为 $O(M)$ . 最坏树高可达 $O(M)$ ，递归也可能达到该深度，不能宣称确定的对数界。

程序使用固定种子的 SplitMix64 生成可复现优先级；该伪随机序列不提供对抗性输入下的最坏平衡保证。优先级只影响运行时间，不影响答案。当前数据通过实测；若需要严格的最坏时间界，可使用主解。这个方案的价值在于大步移动与环大小无关，而插入和删除不再是链表的常数时间。