# 晶块链表 题解

> 备用方案：有序区间表。Codex（GPT-6）采用的解法，程序见 [alternative.cpp](alternative.cpp)；与出题人解法的比较见[主题解](solution.zh.md)。

解法贡献：Codex（GPT-6）补充有序区间表这一替代方案，给出被删除区间的摊还计数，并处理空链表。出题人解法为同类标记线段树，两者渐进复杂度相同；区间分段与平衡搜索树均为已有方法。


## 按种类分段

用有序映射保存每段的起点和种类，另在 $n+1$ 放置一个哨兵。相邻两个起点之差就是前一段的长度。初始化时合并连续相同种类的位置。

必须按种类保存，而不是按能量保存。不同种类即使当前能量相同，之后也可能被分别改能量，不能因此视为同一种类。

维护独立数组 $e_c$ .操作 1 只修改这一数组，已有区间的种类标识不变。

## 一次替换

先在 $r+1$ 和 $l$ 处分裂已有区间，使需要替换的范围恰好对应一段完整的映射元素。分裂不会改变任何位置的种类。

遍历被覆盖的每一段。若长度为 $t$ 、种类为 $a$ ，它的贡献为

$$t\cdot|e_a-e_c|$$

求和后删除这些段，再插入起点为 $l$ 、种类为 $c$ 的一段。即使贡献为零也要执行替换。实现不强制把相邻同类段重新合并；它们仍正确表示序列，且不会破坏下述复杂度界。

## 为什么遍历很多段仍然足够快

初始段数不超过 $n$ .每次替换只会在两个端点分裂至多两段，并插入至多一段，因此整个操作序列创建的段数是 $O(n+m)$ .

一次替换中遍历的每一段紧接着都会被删除，同一映射元素不可能再次被遍历删除。因此所有替换累计遍历和删除的段数也是 $O(n+m)$ ，与随机数据无关。单次替换可能是线性的，但整个序列有摊还保证。

初始化按起点递增、使用正确插入提示建立映射，耗时 $O(n)$ .每次替换只额外进行常数次 $O(\log(n+2))$ 的查找和插入，有序映射的区间删除耗时为查找开销加删除元素数。总时间为 $O(n+k+m\log(n+2))$ ，空间为 $O(n+k)$ .

任何分数都不超过 $49999n$ ，需用 64 位整数保存。$n=0$ 时只存在哨兵，合法输入不会调用区间替换；$k=0$ 时也没有能量操作。

## 正确性与验证

每段始终代表一组种类相同的位置，查表得到的能量就是当前能量；按段累加与逐个位置求和等价，分裂和替换也严格符合操作。独立数组模型验证了等能量异种类、零分替换、能量修改后的再次计分、单点区间、空实例与长区间。

性能测量见[评测环境与性能](../../../docs/评测环境与性能.md)。