# 晶块链表 题解

## 解法与取舍

**出题人解法：同类标记线段树。** 同类标记线段树是首选方案。有序区间表直接维护连续同类段，具有相同的渐进摊还界，作为备用方案。线段树实现须单独处理空序列，不能对空区间递归建树。

**程序与署名：** [std.cpp](std.cpp) 实现出题人解法；Codex（GPT-6）负责实现整理、边界处理与证明说明。Codex（GPT-6）采用的有序区间表见 [alternative.cpp](alternative.cpp) 和[备用方案题解](solution-alternative.zh.md)。

## 维护同类标记的线段树

按位置建立线段树。每个节点要么记录整段唯一的种类，要么标为“混合”；各类能量另存于数组，因此修改某类能量只需修改一个数组元素。替换区间完全覆盖一个同类节点时，以“区间长度乘新旧种类能量差的绝对值”计分，再把该节点标为新种类。遇到混合节点或部分覆盖时向下递归，必要时下传同类标记，返回后合并种类相同的两个孩子。

同类节点的所有位置贡献相同，分到孩子后又恰好划分原区间，所以计分与逐点替换等价。标记始终按种类保存，即使两类能量相等，也仍会执行种类替换。

这不是每次替换都保证访问对数个节点的普通懒标记线段树，但有确定性的摊还界。只统计未被祖先同类标记遮盖的有效混合节点：初始至多 $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 位整数计算乘积与总分。等能量的不同类型仍必须真正替换，因为后续可能分别修改能量。

## 验证与性能

各方案的五次重复计时与峰值内存记录见[评测环境与性能](../../../docs/评测环境与性能.md)。