我写了个线段树233
我们发现对于一个固定的\(k\)，我们可以把原序列分为三段：
- 上升到\(k\)以上
- 想要下降到\(k\)以下但被\(k\)卡住
- 随意上升下降但始终超过\(k\)直到最后
我们为了让最后的结果最大，我们想要最大化第二段后的数。所以我们的操作就等价于选出一个贡献为负的区间\([l,r]\)然后把他贡献变为0。原问题就变成了求最小字段和的问题。
时间复杂度\(O(n)\)
标签：原题,CF1845D,贡献,想要,我们,233 From： https://www.cnblogs.com/fox-konata/p/17637219.html