区间所有子区间的最大子段和之和。
对 \(r\) 扫描线。维护 \([i,r]\) 的最大子段和，做个历史和。
考虑以 \(r\) 为右端点的最大子段和能更新的答案，对于一个区间 \([l,r]\)，其能被更新仅当 \(sum_r-\min\limits_{i=l-1}^{r-1}sum_i>ans_l\) 即 \(ans_l+\min\limits_{i=l-1}^{r-1}sum_i<sum_r\)。
可证明 \(ans_l+\min\limits_{i=l-1}^{r-1}sum_i\) 前面这部分关于 \(l\) 递减。考虑答案组成是 \(\max_{j<i} sum_i-sum_j\)，可简单放缩证明。
于是可以二分出这个 \(<\) 的分界线，修改为一段后缀。现在相当于要支持的操作是，区间赋值 \(a\)，区间令 \(b=k-a\)，区间查询 \(b\) 历史和。还有维护个区间 \(b\) 最小值。
维护矩阵 \(\begin{bmatrix}suma&sumb&hsum&len\end{bmatrix}\)。
区间赋值 \(a\) 即乘上
\[\begin{bmatrix}0&0&0&0\\0&1&0&0\\0&0&1&0\\k&0&0&1 \end{bmatrix} \]区间令 \(b=k-a\) 即乘上
\[\begin{bmatrix}1& -1&0&0\\0&0&0&0\\0&0&1&0\\0&k&0&1 \end{bmatrix} \]更新一次历史和即乘上
\[\begin{bmatrix}1& 0&0&0\\0&1&1&0\\0&0&1&0\\0&0&0&1 \end{bmatrix} \] 标签：begin,end,子段,sum,Henceforth,bmatrix,ans From： https://www.cnblogs.com/Terac/p/18539084