# 变量列表：编号索引与双向链表

出题人解法：编号对应结点池下标，用前后指针维护多个双向链表。Codex（GPT-6）：显式初始化、稳定结点存储、编号合法性及空表边界验证。

## 存储与操作

为每个列表保存头、尾指针。结点保存前驱、后继、备注、所属列表及存活标记。结点池下标等于变量编号，最大已分配编号只递增。

令 $C=\sum c_i$ .读入操作数 $m$ 后，一次性创建容量为 $C+m+1$ 的结点数组。最多只有 $m$ 次插入，因此这个容量足够；之后不扩容，所有指针始终稳定。初始化也使用尾插入，按题目顺序建立编号。

- 查询：先检查编号在已分配范围内且存活；不合法时输出三个 `NULL` .合法时分别查看两个相邻指针及自身备注。
- 删除：把前驱的后继改为当前后继，把后继的前驱改为当前前驱。缺少前驱时更新表头，缺少后继时更新表尾，再清除存活标记。
- 头插入、尾插入：新建编号，连接对应端点。原表为空时同时设置表头和表尾。
- 修改：只修改合法存活结点的备注，不改编号或链接。

## 不变量与正确性

始终维护：每个列表从头沿后继可按当前顺序访问所有存活变量；相邻两结点的前后指针互相对应；表头无前驱、表尾无后继；空表的两个端点都为空。编号池还保持每个已分配编号对应唯一结点。

初始化逐项尾插入满足不变量。插入只新增一个端点及其相邻关系；删除只把被删结点两侧重新接上，并处理端点情况；修改不影响结构。非法操作不改变状态。因此每次操作后不变量仍成立，查询读到的三个位置正是题目要求。

## 复杂度与注意事项

每次操作为最坏 $O(1)$ 时间。总时间和空间都是 $O(n+C+m)$ ，包括一次性结点池初始化和全部输入。最多分配 $10^6$ 个实际结点，另有一个未使用的零号槽位。

检查顺序必须先确认编号范围，再访问结点池，避免负数和大编号越界。删除后即使旧结点仍在池中，也须根据存活标记拒绝访问。新编号不能复用已删除结点。使用堆上数组而非大型局部栈数组；所有指针和标记显式初始化。

程序见 [std.cpp](std.cpp)。数组下标链接、显式指针和标准库链表都能表达同一邻接维护算法，这里采用出题人的显式指针方案；仅替换容器不另列算法。平衡搜索树需要额外排序键并增加操作代价，当前操作集没有这种需求。正式数据覆盖删空再插入、重复删除、未来编号、相同备注、百万累计编号与最大操作数。

测试配方见 [plan.json](tests/plan.json)，生成方式见[数据生成说明](../../../README.md#使用题目文件)。参考环境、逐次测量和适用范围见[评测说明](../../../docs/评测环境与性能.md)。