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