晶块链表题解¶

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

解法贡献：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\) 时也没有能量操作。

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