题解

思路

把 test 看成跳边

若某个 test 从位置 $p$ 开始且不修改 $a_p$，它的长度必须是 $a_p+1$，所以下一个 test 从

开始。若修改 $a_p$，则下一位置可以任选为任意 $q>p$，代价为一。

对后缀 $[a_i,\ldots,a_n]$，位置 $i$ 只是要求 test 数量。尾部 $i+1..n$ 是一条从 $i+1$ 走到 $n+1$ 的路径，每条边对应一个 test。

答案不会超过二

总可以把 $a_i$ 改为 $1$，再把 $a_{i+1}$ 改为剩余长度减一，所以答案只可能是 $0,1,2$。

完全不修改的自然链

令 good[p] 表示从 $p$ 出发连续走自然边能恰好到达 $n+1$，cnt[p] 表示沿途 test 数。倒序递推即可。

若 good[i+1] 且 cnt[i+1]=a_i，答案为零；若 good[i+1] 但数量不同，只改 $a_i$ 即可，答案为一。

尾部只修改一次时最多能分成多少段

令 best[p] 表示从 $p$ 到 $n+1$、至多修改一个 test 头时最多能得到的 test 数。

若在 $p$ 立刻修改并跳到某个自然链起点 $q>p$，能得到 $1+cnt[q]$ 段。令

则这一选择为 $1+T(p)$。

也可以保留 $p$ 的自然边，并把唯一修改留给后面，因此

第二项只在 $nxt_p\le n+1$ 时存在。

对同一 cnt 值记录最大的 good 位置。随着 cnt 增大，这些最大位置严格递减，所以可以二分求出满足位置大于 $p$ 的最大 cnt，即 $T(p)$。

若尾部原本不完整，但 $a_i\le best[i+1]$，就能只改一个内部 test 头构造恰好 $a_i$ 段；否则需要两次操作。

做法

子任务 1：分段最短路动态规划

对每个后缀枚举所有 test 边和段数，直接计算最少修改数，复杂度 $O(n^4)$。

子任务 2：二次扫描求 $T(p)$

先求 good/cnt，再对每个 $p$ 扫描所有 $q>p$ 取最大 cnt[q]，复杂度 $O(n^2)$。

子任务 3：单调位置数组二分

记录每个自然链长度的最右起点，用二分求全部 $T(p)$，总复杂度 $O(n\log n)$。

正确性证明

引理 1：任意后缀变成 multitest 的答案不超过二。

证明：把首元素改为一，再把第二个元素改为后缀剩余长度减一，就得到只含一个 test 的 multitest。

引理 2：good[p] 与 cnt[p] 恰描述从 $p$ 开始不修改任何 test 头的唯一自然分段。

证明：未修改的 test 长度被其首元素唯一确定，因此自然边唯一；倒序递推与这条唯一路径完全一致。

引理 3：best[p] 的递推式正确。

证明：唯一修改若发生在 $p$，可跳到任意 $q>p$，后缀必须是自然链，最优为 $1+T(p)$；否则第一条边必须是自然边，剩余最优为 $1+best[nxt_p]$。两类互斥且覆盖全部方案。

引理 4：尾部不自然完整时，只修改一个内部头能得到的 test 数恰为 $1..best[p]$。

证明：固定修改位置时，可选择任意满足 good[q] 的后继；自然链长度从零到可用最大值连续存在，各修改位置产生的区间起点连续，因此并集为从一开始的连续区间。

定理：算法对每个后缀输出最少操作数。

证明：零操作由引理 2 精确判定；若只需改首元素或 $a_i\le best[i+1]$，由引理 3、4 可用一次操作。其余情形零或一次均不可能，而引理 1 保证两次可行。

复杂度

• 子任务 1：$O(n^4)$ 时间，$O(n^2)$ 空间。
• 子任务 2：$O(n^2)$ 时间，$O(n)$ 空间。
• 子任务 3：每组 $O(n\log n)$ 时间，$O(n)$ 空间。