简要题意
给定一个长度为 $n$ 的序列 $a$，将 $a$ 划分为 $k$ 个连续段，最大化满足连续段中元素和 $\geq s$ 的连续段数。
题解
首先发现是恰好 $k$ 个连续段，这种类型的题套路地考虑 wqs 二分，然后你会惊喜的发现这玩意不是凸的，我的思考也就卡在这里了。
正确的做法是观察到答案具有单调性，所以可以考虑先二分答案转为判定性问题。这时候问题就被转化为，在令答案为 $x$ 的前提下，是否能够划分出 $k$ 个连续段。可以考虑更形式化地描述这个问题，具体的，设 $f_x$ 表示选出 $x$ 段的最小代价，每一段的代价使用 $r-l$ 来刻画，不难发现能够划分出 $k$ 个连续段等价于 $f_x\leq n-k$。所以可以考虑快速求出 $f_x$。
发现 $f_x$ 也是求出恰好答案为 $x$ 的方案数，而且这个函数看起来就是凸的。感性理解就是优先选择代价小的，更加严谨的证明可以参考官方题解。所以可以对 $f$ 进行 wqs 二分。然后内层的 dp 就是套路地记录一个 pair 表示最小代价和对应的最小个数，转移要么不选当前点，要么选以当前点为右端点的代价最小的一个区间，从对应位置转移。这一部分比较简单。
然后就做完了，时间复杂度 $O(n\log^2 n)$，可以通过本题。
标签：二分,题解,最小,连续,答案,ARC168E,代价 From： https://www.cnblogs.com/Harry27182/p/17844883.html