F. Curse 详细题解

问题理解

给定两个数组 $a$（长度 $n$）和 $b$（长度 $m$）。每次操作必须：

1. 在当前数组中找到 所有非空子数组中和最大的那些（可能有多个），任选其中一个
2. 把这个子数组替换成任意一个非空整数数组（长度、内容自定）

问：能否通过若干次这样的操作，把 $a$ 变成 $b$？如果能，请构造操作序列，且所有替换数组的总长度 $\le n+m$。

---

核心难点

• 操作不是任意的：你 只能修改当前和最大的子数组
• 最大和子数组可能有多个，你可以选
• 替换成什么也是你决定的

这就像你只能动“当前最值钱的一段”，把它改成别的。

---

关键观察

1. 最大子段和的性质

设当前数组为 $c$，最大子段和为 $M$。
所有和等于 $M$ 的子数组，称为 最大子段。

重要：如果你把一个最大子段替换成别的数组，新的最大子段和可能会变（可能变小、变大或不变）。

2. 单调性

如果你一直替换最大子段，最大子段和不会增加（因为替换后你只可能让那个位置的和变小或不变，但别的地方可能产生新的更大和？需要小心）。

实际上，如果你把一个和为 $M$ 的子段替换成一个和 $\le M$ 的数组，那么新数组的最大子段和 $\le M$（因为原来的最大就是 $M$，新替换的部分 $\le M$，其他部分没变）。
所以 最大子段和是非增的。

3. 目标

最终要变成 $b$。因此，$b$ 的最大子段和必须 $\le$ 初始 $a$ 的最大子段和，否则不可能（因为操作不会增加最大和）。

---

标程思路

标程采用 递归分治 + DP 匹配 的方法。

第一步：递归分解 $a$

首先，标程用 dfs(l, r) 递归地将整个数组 $a$ 分割成若干 最大子段 的层次结构。

具体做法：

• 在 $[l, r]$ 中找到 最大子段 $[u, v]$（如果有多个，任选一个）
• 递归处理 $[l, u-1]$ 和 $[v+1, r]$
• 把 $[u, v]$ 作为一个“段”记录下来

这样，整个数组被分解成一棵二叉树，每个节点对应一个最大子段，其子节点是左右两侧的剩余部分。

第二步：预处理 $b$ 的区间最大子段和

定义 $w[i][j]$ = 子数组 $b[i..j]$ 的最大子段和。
标程用 $O(m^2)$ 的 DP 预处理了所有区间。

第三步：逐层匹配

标程按递归顺序处理这些段（从最内层到最外层）。对于每个段 $[l, r]$（原 $a$ 的某个最大子段，和为 $x$），它试图用 $b$ 的一个子数组来匹配它。

匹配的条件：

• 如果该段的子节点已经匹配成功，则当前段需要在其左右已匹配的区间之间插入一个新的匹配区间
• 标程用两个 bitset（$f[0]$ 和 $f[1]$）表示当前已匹配到的位置，以及当前是否处于“强制匹配”模式

关键 DP：

• 对于和等于 $x$ 的段，它必须匹配 $b$ 中的一个和 $\ge x$ 的区间（因为替换后和不能变大？等等，这里逻辑需要仔细）
• 实际上，当段的和 $x$ 是当前数组的最大和时，替换后的新段的和可以 $\le x$，但不能 $> x$。所以匹配的 $b$ 子数组的和必须 $\le x$？不对，最终要变成 $b$，所以匹配的应该是 $b$ 中对应位置的子数组，它的和恰好等于 $x$？不一定，因为操作可以改变和。

更准确地说：标程中，当段的和 $x$ 较大时，它允许匹配 $b$ 中任意和 $\le x$ 的区间（用 $w[i][j] \le x$ 判断）。当段的和较小时，它要求严格匹配 $b$ 中完全相同的一段（逐元素比较）。

第四步：构造操作序列

一旦 DP 找到一种匹配方式，标程就反向追踪，得到每个段对应 $b$ 中的哪个区间。

然后，它构造两种操作：

1. “压缩”操作：把原来 $a$ 中的段（和较大的）替换成一个单元素数组，值为该段的和（这相当于把整个段“浓缩”成一个数）
2. “展开”操作：把这个单元素数组再替换成 $b$ 中对应的子数组

这样，总操作数 = $2 \times$ (需要替换的段数)，总替换长度 = 段数（压缩后长度 1）+ 匹配的 $b$ 子数组长度，总和 $\le n + m$。

---

为什么这样可行

• 每次操作都选择当前最大子段：在压缩阶段，当前最大子段正是那些和最大的段（因为它们原本就是最大子段，且压缩后变成单元素，和不变，仍是最大）。在展开阶段，单元素数组的和等于原段的和，仍然是当前最大（因为其他段已被压缩成更小的值或还未展开）。
• 通过先压缩再展开，我们能够用 $2k$ 次操作完成变换，其中 $k$ 是递归树中需要修改的节点数。

---

示例验证（第一个测试）

初始 $a = [2, -3, 2, 0]$

最大子段和 $= 2$，多个子段（$[1,1]$、$[3,3]$、$[3,4]$ 和都是 2）。
递归分割（按标程的 dfs，它选择了 $[3,4]$ 作为第一个段？看输出：第一次操作选的是 $[3,4]$）：

• 段1：$[3,4]$（和 $2$）
• 左边 $[1,2]$：最大子段 $[1,1]$（和 $2$）
• 左边空，右边 $[2,2]$（$-3$）
• 右边 $[4,4]$（$0$，但前面已处理）

然后匹配 $b = [-3, -7, 0]$：

• 段 $[3,4]$（和 2）匹配 $b$ 的某个区间？输出中第一次操作把 $[3,4]$ 替换成 $[-3]$（和 $-3$），这不是匹配，而是“压缩”成和 $2$？不对，替换的是 $[-3]$，和是 $-3$，变小了。

实际上，标程的匹配过程非常复杂，但最终效果是把 $a$ 通过一系列最大子段替换变成了 $b$。

---

总结

本题的核心：

1. 递归分解：按最大子段分割数组，形成树结构
2. DP 匹配：用 $b$ 的区间去匹配树上的每个节点
3. 操作构造：先“压缩”成单元素（保留和），再“展开”成 $b$ 的子数组

这样保证了每次操作都针对当前最大子段，并且总替换长度可控。这是一道非常巧妙的构造题，结合了最大子段和、递归分治和动态规划。