晶块链表 题解¶
解法与取舍¶
出题人解法：同类标记线段树。 同类标记线段树是首选方案。有序区间表直接维护连续同类段，具有相同的渐进摊还界，作为备用方案。线段树实现须单独处理空序列，不能对空区间递归建树。
程序与署名： std.cpp 实现出题人解法；Codex（GPT-6）负责实现整理、边界处理与证明说明。Codex（GPT-6）采用的有序区间表见 alternative.cpp 和备用方案题解。
维护同类标记的线段树¶
按位置建立线段树。每个节点要么记录整段唯一的种类，要么标为“混合”；各类能量另存于数组，因此修改某类能量只需修改一个数组元素。替换区间完全覆盖一个同类节点时，以“区间长度乘新旧种类能量差的绝对值”计分，再把该节点标为新种类。遇到混合节点或部分覆盖时向下递归，必要时下传同类标记，返回后合并种类相同的两个孩子。
同类节点的所有位置贡献相同，分到孩子后又恰好划分原区间，所以计分与逐点替换等价。标记始终按种类保存，即使两类能量相等，也仍会执行种类替换。
这不是每次替换都保证访问对数个节点的普通懒标记线段树，但有确定性的摊还界。只统计未被祖先同类标记遮盖的有效混合节点：初始至多 \(O(n)\) 个；一次操作只有两个区间边界附近的 \(O(\log(n+2))\) 个节点可能变成新的混合节点。被完整覆盖而向下展开的混合节点，操作后都变为同类，可将这部分遍历记在消失的混合节点上。因此全部操作总时间为 \(O(n+k+m\log(n+2))\) ，空间为 \(O(n+k)\) ，其中 \(n\) 是位置数、\(k\) 是种类数、\(m\) 是操作数。
实现边界¶
类型编号从一开始，混合节点用零表示。下传同类标记时覆盖两个孩子，返回后仅在孩子类型相同时合并。修改类型能量只改查表数组，不遍历线段树。
若 \(n=0\) ，跳过建树；合法输入不会发起区间替换。若 \(k=0\) ，也不存在能量修改。每次得分至多为 \(49999n\) ，用 64 位整数计算乘积与总分。等能量的不同类型仍必须真正替换，因为后续可能分别修改能量。
验证与性能¶
各方案的五次重复计时与峰值内存记录见评测环境与性能。