ARC085D NRE

发表于 更新于 分类于 ， ， 阅读次数：

题意：给定长为 的 数组 。

有一个长度同为 的数组 ，初始时为全 。

给定 个区间，可以选择若干区间，将 中区间内的元素置为 。

最小化 的值。

，时限 。

注意到 均为 数组，则

此时不需要考虑 的贡献。

只有 正难则反

其中 是定值，于是我们只需最小化：

考虑 ，记 表示考虑了所有 的区间，最右覆盖到 ， 的贡献最小值。

特殊地，若没有向右覆盖，则 记为 。

从 转移至 时 ：

  • 不选区间：

  • 选择区间。枚举在 开头的区间 ，有：

可以用线段树维护，复杂度为 。