最大 K 子段和

支持区间覆盖和区间内选至多 k 个不相交子段;线段树维护最大/最小子段和,反复取最大子段并取反。

标签 贪心 / 反悔贪心 / 线段树 / 区间覆盖 / 最大子段和

题目描述

给定长度为 𝑛 的整数序列 𝐴,维护 𝑞 次操作:

  • 0 l r v:把 𝐴𝑙,…,𝐴𝑟 全部赋值为 𝑣;
  • 1 l r k:在 𝐴𝑙,…,𝐴𝑟 中选出至多 𝑘 个两两不相交的非空连续子段,使这些子段中所有元素之和最大。

可以不选任何子段,此时答案为 0。对每个询问输出最大和。

1≤𝑛,𝑞≤105,|𝐴𝑖|,|𝑣|≤109,1≤𝑘≤20。答案可能超过 32 位整数范围,需使用 64 位整数。

题解

k=1

线段树每个结点维护区间和、最大前缀和、最大后缀和、最大子段和,以及这些量的端点。合并左右儿子时:

  • 区间和直接相加;
  • 最大前缀和取“左儿子的最大前缀和”与“左儿子区间和加右儿子最大前缀和”的较大值;
  • 最大后缀和对称;
  • 最大子段和取左儿子最大子段和、右儿子最大子段和、左儿子最大后缀和加右儿子最大前缀和三者中的最大值。

为了支持区间取反,还要同时维护最小前缀和、最小后缀和、最小子段和及其端点。取反后最大值和最小值互换,再整体取相反数。

区间覆盖时,按区间长度和 𝑣 的符号重算上述最大/最小字段,并记录覆盖标记。覆盖标记下传时直接覆盖左右儿子,并清空取反标记。

k>1

反复执行至多 𝑘 次:

  1. 查询 [𝑙,𝑟] 的最大子段和及其左右端点;
  2. 若最大子段和小于等于 0,停止;
  3. 把该和加入答案,并把该子段整体取反;
  4. 记录这个子段。

询问结束后,把所有记录的子段再取反一次,恢复原序列。每个询问互相独立,不能保留上一次询问的取反结果。

正确性

把序列建成一条单位容量的费用流网络:选择若干不相交子段相当于发送若干单位流量,每单位流量的费用是被选元素之和。每次在残量网络中增广一条最大费用路径,等价于在当前序列中取最大子段;把该子段取反,就是加入反向边。

因此,反复取最大子段并取反,就是在依次做最多 𝑘 次最大费用增广。若当前最大子段和非正,继续增广不会增加答案,可以停止。最终得到的就是至多 𝑘 个不相交子段的最大和。

复杂度

建树为 𝑂(𝑛);单次区间覆盖为 𝑂(log𝑛);单次询问做至多 𝑘 次查询和取反,每次 𝑂(log𝑛),共 𝑂(𝑘log𝑛)。空间为 𝑂(𝑛)。

参考

源码位置