数列分段 III

太菜了，只会打暴力。

首先考虑二分答案。

我们发现，有一个结论：如果每段和都小于 \(mid\)，那么可行划分的段数构成的集合 \(S\) 一定是一段区间。

接下来证明。

严谨证明太难写了，下面是半成品，没写完。

说人话，就是归纳。假设前 \(i - 1\) 个前缀满足，说明第 \(i\) 个前缀也满足。

我们把并起来还是区间的两个区间连一条边，只要能转移的 \(j\) 都在一个连通块就一定是区间。

显然一个区间能转移到的区间都和它连通。

然后把能转移的 \(j\) 分为 \(sum_j < sum_i\) 和 \(sum_j \ge sum_i\) 的。

能转移到后者的都能转移到 \(i\)，而且后者一定和某一个 \(sum\) 比它小的连边，说明后者一定和某一个前者连通。

接下来需要说明前者之间连通，对于 \(k < j\)，显然 \(k\) 能转移到 \(j\)。