1. 问题理解

我们有一个长度为 $N = 2^k$ 的内存，初始全 $0$。

目标状态由 游程编码（Run-Length Encoding, RLE） 给出：

$c_1$ 个 $v_1$，接着 $c_2$ 个 $v_2$，…，$c_n$ 个 $v_n$。

总长度 $\sum_{i=1}^n c_i = 2^k$。

允许的操作：

$\mathtt{STORE}([l, r], x)$，其中 $[l, r]$ 必须是 正确的内存段，即长度 $len = r-l+1 = 2^i$，且 $l$ 是 $len$ 的倍数。

要求：最少操作次数。

---

2. 正确内存段的性质

正确内存段其实就是 完全二叉树上的节点对应的区间。

整棵树根节点：$[0, 2^k-1]$（长度 $2^k$）。

每个节点 $[L, R]$ 的长度是 $2^i$，$L$ 是 $2^i$ 的倍数。

它可以分成两个子节点：$[L, M]$ 和 $[M+1, R]$，其中 $M = L + 2^{i-1} - 1$（长度 $2^{i-1}$）。

---

3. 思路

初始全 $0$，目标状态是给定的 RLE 序列。

操作是覆盖一个正确内存段为同一个值 $x$。

我们要用最少的覆盖操作得到目标状态。

3.1 从目标倒推（贪心合并） 一个常见思路：从目标状态出发，考虑如果两个相邻块的值相同，并且它们可以合并成一个 正确的内存段，那么我们可以用一次操作覆盖它们，而不是两次。

但这里要注意：我们可能先覆盖大的区间，再覆盖小的区间来修正，但这样可能不是最优。 实际上，我们可以用 自底向上 的树形 DP 来考虑。

---

4. 树形 DP 模型

把整个内存 $[0, 2^k-1]$ 看作一个满二叉树的根。

定义 $dp[u]$ 表示：把以节点 $u$（对应某个正确内存段）变成目标状态中该段的值所需的最少操作次数。

如果 $u$ 是叶子（长度 1），那么如果目标值等于初始值 0，则 $dp[u] = 0$，否则 $dp[u] = 1$。

如果 $u$ 是非叶子，它有两个孩子 $left$ 和 $right$。

设 $val[u]$ 表示目标状态中这个段是否 整个段都是同一个值（即该段在目标状态中所有单元值相同）。

如果 $val[u]$ 存在（设为 $x$），那么我们可以用一次操作 $\mathtt{STORE}(u, x)$ 覆盖整个段，然后不需要在子树里再操作，所以 $dp[u] = 1$。

否则，我们必须分别处理左右孩子：$dp[u] = dp[left] + dp[right]$。

但是注意：如果左右孩子的目标值相同，并且这个值和用一次操作覆盖 $u$ 的值相同，我们可能可以节省一次？ 其实这里要小心：如果 $val[left] = val[right]$ 且不为空，那么 $val[u]$ 就应该等于这个值，所以这种情况已经被 $val[u]$ 存在的情况覆盖了。 所以不需要额外判断。

关键：$val[u]$ 怎么求？ 我们预先知道整个目标数组（通过 RLE 展开？但 $k$ 最大 30，$2^{30}$ 太大不能显式展开）。 所以必须 不显式展开数组 而判断某个正确段是否在目标状态中值全相同。

---

5. 不显式展开判断段的值一致性

一个正确段 $[L, R]$ 的长度是 $2^i$。

我们有一个 RLE 序列 $(c_1, v_1), (c_2, v_2), \dots$。

我们可以通过 前缀和 快速定位 $L$ 和 $R$ 所在的 RLE 块。

如果 $[L, R]$ 完全包含在某个 RLE 块内，那么 $val = v_{\text{那个块}}$。

否则，$val$ 不存在（即该段内目标值不统一）。

判断方法：

设 $pos[i]$ 表示第 $i$ 个 RLE 块的结束位置（0-indexed 的右端点），即 $pos[0] = c_1 - 1$， $pos[1] = pos[0] + c_2$，… $pos[j] = \sum_{t=1}^{j+1} c_t - 1$。

对于区间 $[L, R]$：

找到 $L$ 所在的 RLE 块 $p_L$，使得 $pos[p_L-1] < L \le pos[p_L]$（注意边界）。

找到 $R$ 所在的 RLE 块 $p_R$。

如果 $p_L = p_R$，那么整个区间在同一个 RLE 块，值相同 $= v_{p_L+1}$。

否则，如果 $p_L + 1 = p_R$，还要检查 $L$ 是否在 $p_L$ 块末尾，$R$ 是否在 $p_R$ 块开头，并且 $v_{p_L+1} = v_{p_R+1}$ 吗？ 其实更简单：只要 $[L, R]$ 跨过 RLE 块边界，并且这些块的值不全相同，那么 $val$ 就不存在。 但注意：如果 $[L, R]$ 覆盖了多个块，但这些块的值都一样，那么 $val$ 存在。

所以准确条件：

$val[L, R]$ 存在，当且仅当 $[L, R]$ 包含的所有 RLE 块的值都相同。

---

6. 算法步骤

预处理 RLE 块的前缀和 $prefix$，$prefix[i] = \sum_{j=1}^i c_j$，$prefix[0]=0$。

构建一个递归函数 $solve(L, R)$ 计算 $dp$ 和 $val$ 对于正确段 $[L, R]$。

长度 $len = R-L+1$。

用前缀和找到 $[L, R]$ 覆盖的 RLE 块：

设 $start_block$ = 最小的 $j$ 使得 $prefix[j] > L$，其实更准确： 块 $i$ 对应区间 $[prefix[i-1], prefix[i]-1]$。 我们找 $L$ 在哪个块：二分查找最小的 $i$ 使得 $prefix[i] > L$，则 $bl_L = i$。 同样找 $R$ 在哪个块：最小的 $i$ 使得 $prefix[i] > R$，则 $bl_R = i$。

如果 $bl_L = bl_R$，则 $val = v[bl_L]$。

否则，检查 $v[bl_L], v[bl_L+1], \dots, v[bl_R]$ 是否全相同，如果是，$val = v[bl_L]$，否则 $val = \text{None}$。

如果 $val$ 存在，则 $dp = 1$。

否则，$mid = L + len/2 - 1$， $dp = solve(L, mid) + solve(mid+1, R)$。

返回 $dp$。

---

7. 复杂度

递归深度 $O(k)$。

在每一段判断值一致性时，最坏需要遍历 $O(n)$ 个 RLE 块？ 但这里可以优化：我们预先记录 RLE 中值变化的边界，用区间最小值/最大值查询（Segtree 或 Sparse Table）在 $O(1)$ 判断一个段内的 $v$ 是否全相同。 具体：对 RLE 序列 $v[1..n]$，我们想查询 $v[bl_L .. bl_R]$ 的最小值 $minv$ 和最大值 $maxv$，如果 $minv = maxv$ 则全相同。

预处理 $O(n \log n)$，每个节点判断 $O(1)$，总节点数 $O(2^{k+1})$ 但 $k \le 30$ 太大？ 不对，正确内存段的总数是多少？ 长度为 $2^i$ 的段有 $2^{k-i}$ 个，$i=0..k$，所以总数为 $\sum_{i=0}^k 2^{k-i} = 2^{k+1} - 1$。 当 $k=30$，节点数约 $2^{31}-1$ 太大，不能显式递归所有节点。

---

8. 优化：只递归必要的节点

很多节点的 $val$ 可能直接存在，不需要递归到叶子。

我们可以在递归时，如果发现当前段 $[L, R]$ 在目标状态中值全相同，就直接返回 1，不递归子节点。

这样，递归只会沿着 值变化的边界 进行，节点数最多 $O(n \cdot k)$？ 因为每个 RLE 块边界会生成 $O(k)$ 个递归节点。

这样可行。

---

9. 总结

我们利用 正确内存段 = 满二叉树的节点 这一结构，采用分治 + 记忆化搜索， 仅递归那些在目标状态中值不一致的段，利用 RLE 和 ST 表快速判断段内值一致性， 从而在 $O(n \log n + nk)$ 时间内解决问题。

最终答案 = 递归计算 $solve(0, 2^k - 1)$ 的结果。