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

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

程序：alternative.cpp。本方案与双向循环链表并列，支持完整数据。

将环表示为序列¶

任取一个环的切口，按方向 \(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 生成可复现优先级；该伪随机序列不提供对抗性输入下的最坏平衡保证。优先级只影响运行时间，不影响答案。当前数据通过实测；若需要严格的最坏时间界，可使用主解。这个方案的价值在于大步移动与环大小无关，而插入和删除不再是链表的常数时间。