rt。求助，大佬们~

如果必须对$a$求解，目前还没想到好的方法。但是如果可以选择$a$任意长度的前缀求解，则有$O(n\log n\log V)$的方法。

设 $f_{i}$ 为 $a_{1\sim i}$ 最多可以分多少段，使得每段的和都 $\le mid$。

则有转移 $f_{i,j}=\max(f_{j}+1)$，其中 $j$ 满足 $j<i,S_{i}-S_{j}\le mid$（$S$ 是 $a$ 的前缀和数组）。

如果存在 $f_{i}\ge m$，则说明合法，这是因为如果$f_i>m$，则必定存在$j<i$，使得$f_j=m$。

这里也是为什么难以只对$a$求解，因为有负值所以不满足单调性（即$f_i$合法$\nRightarrow f_{i+1}$也合法），因此如果定义$f$为最大分段数则只能求得$a$所有前缀的答案，如果要仅求$a$的答案，必须将$f$所有可能的取值都计算出来，这样还得再乘一个$O(n)$。

这样时间复杂度是 $O(n^2\log V)$，时间开销主要再 $O(n)$ 的转移，考虑优化。

$S_{i}-S_{j}\le mid\iff S_{j}\ge S_{i}-mid$。我们考虑用 $S_{u}$ 作为索引，$f_{u}$ 作为值，扔到线段树里。

更新的时候求线段树 $(S_{i}-mid)\sim V$ 的最大值 $maxx$，用 $maxx+1$ 更新 $f_{i}$ 即可。

因为 $V$ 太大，所以要将所有用到的下标（即 $S_{i}$ 和所有 $S_{i}-mid$）离散化。

时间复杂度降至 $O(n\log n\log V)$。

也可以用树状数组代替线段树，虽然树状数组无法维护区间最大值，但是每次询问的区间都是一个后缀，所以只需要反向建立树状数组即可，码量和速度上都优于线段树。

线段树实现：https://paste.ubuntu.com/p/NKCTF6TVkK/

树状数组实现：https://paste.ubuntu.com/p/wsBNqzgtxf/