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

出题人解法：双向循环链表，移动取模并选较短方向。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。隐式 Treap及其 alternative.cpp按排名移动，只需常数次整数运算；插入、删除、查询的期望时间为 \(O(\log(n+m))\) . 它不依赖步数上界，代价是更多存储、树操作和对随机优先级的平衡假设。两者并列提供，均通过完整数据；有当前步数保证时，链表作为首选，具有直接且确定的操作界。

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