资讯详情

CF1136E

这几把什么题目？？

有取 \(\max\) 还有神秘 \(+k_i\) 看起来很难做啊，想了半个小时完全没思路。

你发现思维的卡点在于，你完全无法维护一个任意的向前取 \(\max\) 状物。这个时候我们需要一个具有单调性的东西。

令 \(b_i = a_i - \sum\limits_{j=1}^{i-1} k_j\)，我们又有 \(a_{i-1} + k_{i-1} \le a_i\)，代入：\(b_{i-1} + \sum\limits_{j=1}^{i-1} k_j \le b_i + \sum \limits_{j=1}^{i-1} k_j\)，得到 \(b_{i-1} \le b_i\)。

因此我们使用区间覆盖区间求和的线段树维护 \(b\)，再维护 \(k\) 的二次前缀和即可。