# 题解：可修改环上的边权游戏

出题人数据结构：按隐式下标维护序列的伸展树与区间最小值。Codex（GPT-6）修正胜负判据，给出完整策略证明，补齐短环规则，并维护最小值首次和末次出现的位置，使每次编辑后的判定为常数时间。

## 胜负只需要哪些信息

空环必败。对于非空边权序列，记最小值为 $\mu$ ，从起点顺时针走到第一条最小值边之前的边数为 $L$ ，逆时针的对应边数为 $R$ .它们是最小值首次出现前、末次出现后的元素数量。

- 若所有边均为正且 $n$ 为奇数，先手必胜。
- 其余情况，先手必胜当且仅当 $L,R$ 至少一个为奇数。

权值可以任意减小，不能只分析每次减一的玩法。下面直接证明每个必胜状态有一步能走到必败状态，而每个必败状态的所有走法都到必胜状态。

## 已有零权边

零边不可走，棋子可活动的部分是一条路径。左右两侧离边界分别有 $L,R$ 条正权边。

若一侧长度为奇数，沿该侧第一条边移动并清零。对手的一侧立即被堵住，另一侧剩偶数条边，成为两侧均为偶数的状态。

若两侧都是偶数，任意合法移动沿某个正的偶数长度方向前进一步。前方剩余长度变成奇数。若把刚走过的边清零，后方长度为零；若仍保留正权，后方长度增加一，也变为奇数。因此对手必然获得至少一侧为奇数的状态。路径长度全零时确实没有合法移动，作为终止情形与判据一致。

## 所有边均为正

若 $n$ 为奇数，任选一条相邻边移动并清零。对手得到一条长为 $n-1$ 的偶数路径，位于端点；由上一节它必败。

以下令 $n$ 为偶数。若 $L$ 为奇数，则起点顺时针第一条边严格大于 $\mu$ .沿它移动，并把它减为 $\mu$ .新位置顺时针第一条最小边前有 $L-1$ 条边，逆时针紧邻刚走过的最小边；两个数量均为偶数。$R$ 为奇数时对称操作。

反之，假设 $L,R$ 均为偶数。考虑顺时针移动，减权后的值为 $v$ ：

- 若 $v<\mu$ ，这条刚走过的边成为唯一最小边。它位于新位置的逆时针相邻处，顺时针则要先经过 $n-1$ 条边，为奇数。$v=0$ 时同样由路径判据得到必胜。
- 若 $v\ge\mu$ ，被走过的边此前不是最小边，所以 $L>0$ .之前顺时针第一条最小边仍在前方，到它之前只剩 $L-1$ 条边，为奇数。

逆时针移动完全对称。因此从两个偶数的状态不能走到另一个必败状态。结合边权总和严格下降，上述策略证明了判据。

一条正权自环可直接清零，所以必胜。两条平行边套用判据，结果是权值相等时必败，否则必胜，与两个堆的直接博弈一致。

## 隐式伸展树

按边的当前顺序维护伸展树。每个辅助子树保存节点数、最小值、最小值在其中首次和末次出现的下标。由左右子树与根合并这些量，旋转时局部更新即可。

加入两个权值为101的哨兵，分别置于序列两端；所有合法边权至多100，所以非空时哨兵不会影响最小值。按秩找到编辑位置，利用伸展操作执行赋值、插入或删除。插入和删除可先把区间左右边界伸展到根与其右孩子，将待编辑区间隔离出来。

根处记录的位置包含左哨兵：若首次最小值下标为 $f$ 、末次为 $l$ ，两者均从零开始，则 $L=f-1$ 、$R=n-l$ .因此查询判据耗时 $O(1)$ .

建树 $O(n)$ ，每次编辑摊还 $O(\log(n+q+1))$ ，总时间 $O(n+q\log(n+q+1))$ .节点池不回收删除节点，空间为 $O(n+q)$ .建树递归深度为对数，在线旋转与查秩均为迭代。

## 两个错误判据的反例

仅在最小值为0或1时分析位置、其余情况只看环长奇偶，会误判边权 $(2,2,2,3)$ .先手沿权值3的边将其减为2，留给对手全部为2的偶数环，因此先手必胜。

零权情形也必须检查**两侧的奇偶性**。例如 $(0,1,1,1)$ 的逆时针可行路径长为3，先手必胜；仅检查某一侧位置是否为零并不能替代奇偶性。

所以首选仍使用伸展树的数据结构思路，但胜负计算采用上述已证明的完整判据。验证包含权值0至3、长度0至6的全部5461个状态的逐步博弈穷举，以及插入、删除和修改的独立序列模型。见[标准程序](std.cpp)、[测试说明](tests/README.md)及[性能记录](../../../docs/benchmark-R37.json)。