# 机器人指令平台：双向循环链表

出题人解法：双向循环链表，移动取模并选较短方向。Codex（GPT-6）：整理空环不变量、双语证明及验证；补充按排名维护环的隐式 Treap 方案。

## 首选方案

以平台编号作数组下标，为每个平台保存方向 $0$ 的后继和方向 $1$ 的前驱。另存当前编号、有效平台数、历史最大编号。初始链为 $1,2,\ldots,n$ 首尾相接。

插入新节点 $z$ 时，设当前节点为 $u$ 、后继为 $v$ ，将 $u\to v$ 改成 $u\to z\to v$ ，同步修改反向链接。删除 $u$ 时，设前驱为 $p$ 、后继为 $v$ ，连接 $p\to v$ 并将当前节点设为 $v$ . 空环插入时令新节点的两个链接指向自身；删除最后一个节点时令当前编号为零。查询时根据有效数量区分空环。

非空环大小为 $s$ 时，把步数化为 $r=((x\bmod s)+s)\bmod s$ . 如果 $s-r<r$ ，反转方向并走 $s-r$ 步，否则按原方向走 $r$ 步。C++ 对负数取余可能得到负值，因此需要上述非负化。

## 正确性

不变量：每个有效节点的两个链接分别指向环中的后继、前驱，且两种链接互为逆关系；当前编号在非空环中始终有效。初始链满足它。插入替换一对相邻链接，删除连接被删节点两侧，均保持其余邻接关系；单节点及空环按定义处理。故插入、删除和查询正确。

沿任一方向走 $s$ 步回到原处，故去掉整圈不改变终点。正向走 $r$ 步与反向走 $s-r$ 步终点相同，因此较短方向优化也不改变终点。所有操作由此正确。

## 复杂度与比较

令 $B$ 为题目保证的单次最短移动步数上界，本题 $B=500$ . 建链时间为 $O(n)$ ，插入、删除、查询为 $O(1)$ ，移动为 $O(B+1)$ ；总时间为 $O(n+m(B+1))$ ，按全部已发放编号分配的空间为 $O(n+m)$ . 平台删除后不复用编号；不必回收数组槽位。

程序见 [std.cpp](std.cpp)。[隐式 Treap](solution-alternative.zh.md)及其 [alternative.cpp](alternative.cpp)按排名移动，只需常数次整数运算；插入、删除、查询的期望时间为 $O(\log(n+m))$ . 它不依赖步数上界，代价是更多存储、树操作和对随机优先级的平衡假设。两者并列提供，均通过完整数据；有当前步数保证时，链表作为首选，具有直接且确定的操作界。

测试包含空环重建、不复用编号、方向反转、两节点插入、最大正负步数和连续 $500$ 步压力移动。配方见 [plan.json](tests/plan.json)，性能见[评测说明](../../../docs/评测环境与性能.md)。