E. Best Cow Fences -221025
有意思的题目。
因为丢在了二分的链接里，我们思考一下究竟是什么具有单调性。
硬要说的话，平均值的大小是有单调性的。对于平均值最大的区间，若其平均值大于 \(x\)，明显也会大于 \(x-1\)。
这种形式的「单调性」限制了我们的 check 只能朝一个方向写：给出一个平均值 \(x\)，判断是否存在长度 \(\ge L\) 的区间，其平均值大于 \(x\)。
即：
\[\frac{\sum_{i=l}^r A_i}{r-l+1} \ge x \]转化为：
\[\begin{aligned} \sum_{i=l}^r A_i &\ge x\times(r-l+1) \newline A_l+A_{l+1}+\cdots+A_r &\ge x + x + \cdots + x \newline (A_l-x)+(A_{l+1}-x)+\cdots+(A_r-x) &\ge 0 \newline \sum_{i=l}^r A_i-x &\ge 0 \end{aligned} \]所以对于一次 check，我们把所有 \(A\) 中的元素减去 \(x\)，用滑窗找到最大子段和，判断是否大于等于 \(0\) 即可。