CF1175G Yet Another Partiton Problem 是什么问题？

\(\text{Solution}\) 有关斜率优化的强势套娃题，感觉套出了巅峰 我整整写了 5 个小时、、、 简单 \(dp\) \[f_{i,j} = f_{i-1,k-1} + (j-k+1)\max_{l=k}^j a_l \] 固定这个最大值，于是原序列可用笛卡尔树结构表示 考虑左侧对 \(mid\) 的贡献，显然斜率优化维护一个下凸壳即可，找到最小的 \(b=f_k-k a_{mid}\) 左侧对右侧的贡献，此时 \(\max=a_{mid}\)，这个最大值对右侧均有贡献 \(b+a_{mid} \times (j+1)\) 不能把右侧都遍历一边，因为笛卡尔树区间长度和没保证，但注意到贡献是个 \(kx+b\) 的形式，于是可以李超线段树维护。 回溯要合并两个凸包，为保证复杂度，要启发式合并，支持两端插点，用 deque 即可 没了。。。