-
有点被降智了/ll
-
首先区间修改显然先转化成差分序列单点修改。
-
显然对于相同的操作序列，\(a_i\) 的取值对答案无影响，因此我们可以先让 \(a_i\) 全部取 \(0\)，最后再加回来即可
-
假如说操作到某一时刻，\(a_i\) 的值中第一个非 \(0\) 的位置 \(<0\)，则显然这个操作比 \(a_i\) 全 \(0\) 时的序列更优，我们就重新把这个序列定义为”基准序列“，也就是说我们重新让 \(a_i\) 全部变为 \(0\)；否则继续操作
-
维护第一个非 \(0\) 的位置可以使用 \(set\) 解决，复杂度 \(O(n \log n)\)