526互联

CF1887C Minimum Array 题解

发布时间 2023-12-26 17:54:40作者: FOX_konata

Problem - 1887C - Codeforces

Minimum Array - 洛谷

  • 有点被降智了/ll

  • 首先区间修改显然先转化成差分序列单点修改。

  • 显然对于相同的操作序列，\(a_i\) 的取值对答案无影响，因此我们可以先让 \(a_i\) 全部取 \(0\)，最后再加回来即可

  • 假如说操作到某一时刻，\(a_i\) 的值中第一个非 \(0\) 的位置 \(<0\)，则显然这个操作比 \(a_i\) 全 \(0\) 时的序列更优，我们就重新把这个序列定义为”基准序列“，也就是说我们重新让 \(a_i\) 全部变为 \(0\)；否则继续操作

  • 维护第一个非 \(0\) 的位置可以使用 \(set\) 解决，复杂度 \(O(n \log n)\)