题解

思路

先考虑固定子数组。按照从右到左的顺序处理，设右侧已经允许的最大值为 $v$。当前数为 $x$ 时，至少要把它拆成

个正整数，增加 $k-1$ 次操作。把这些部分尽量均匀地排成非递减序列后，最左部分为 $\lfloor x/k\rfloor$，它成为继续向左处理时的新上界。

做法

从右向左枚举子数组左端点，同时维护所有右端点对应的状态。状态由“当前上界、右端点数量、这些子数组的操作数之和”组成。

加入新数 $x$ 时，同一状态中的所有右端点使用相同的 $k$，转移到新上界 $\lfloor x/k\rfloor$，并把操作数之和增加“数量乘 $k-1$”。转移后上界相同的相邻状态合并。不同状态的上界单调，能保持较少的压缩段。每次加入后的全部操作数之和就是以当前位置为左端点的贡献。

极小值域可以枚举每个元素的所有非递减正整数拆分；中等规模可以直接枚举左右端点，并对每个子数组执行从右向左的贪心。

正确性说明

固定右侧上界 $v$ 时，少于 $\lceil x/v\rceil$ 个部分无法使每部分都不超过 $v$；取恰好这么多部分并尽量均匀分配，可以得到非递减拆分，且其最左部分达到可能的最大值 $\lfloor x/k\rfloor$，对更左元素最有利。因此贪心转移同时最小化当前操作数并保留最优后续条件。压缩状态只合并转移结果完全相同的右端点，不改变任何子数组的贡献，最终累加恰为所有非空子数组极端值之和。

复杂度

设值域上界为 $A$。压缩状态数量为 $O(\sqrt A)$，时间复杂度为 $O(n\sqrt A)$，空间复杂度为 $O(\sqrt A)$。