非常精妙的一个题目。
考察操作形式，注意到一定形如操作若干个不交划分区间，使得每个区间都依赖于一个数转移而来，具体证明是，考虑将操作转化为前缀和上的拓展，那么必定拓展成若干个连续段，使得前缀和数组不降，进而得证，根据这一点，可以很简单的写出 \(O(n^3)\) 做法。
我们不以区间为转移终点，不妨将依赖的数字拿出来，设为 \(1 \le i_1 < i_2 < ... < i_k \le n\)，要求 \(b_{i_x} \le b_{i_{x + 1}}\)，此时将移动的贡献拆开，可以得到一个很简单的 \(O(n^3)/O(n^2)\) 做法，但是还是没有实质性的进步。这个时候题解给出了一个很关键的观察：存在最优划分使得 \(b_{i_x + 1} \sim b_{i_{x + 1} - 1} \notin [b_{i_x}, b_{i_{x + 1}}]\)，理解起来也很容易，否则此时从中间找个数划开，那么贡献一定不劣。
使用线段树维护 DP 数组即可，可能还要写个矩阵快速幂啥的？