最大 K 子段和
支持区间覆盖和区间内选至多 k 个不相交子段;线段树维护最大/最小子段和,反复取最大子段并取反。标签 贪心 / 反悔贪心 / 线段树 / 区间覆盖 / 最大子段和
题目描述
给定长度为 的整数序列 ,维护 次操作:
0 l r v:把 全部赋值为 ;1 l r k:在 中选出至多 个两两不相交的非空连续子段,使这些子段中所有元素之和最大。
可以不选任何子段,此时答案为 。对每个询问输出最大和。
,,。答案可能超过 位整数范围,需使用 位整数。
题解
k=1
线段树每个结点维护区间和、最大前缀和、最大后缀和、最大子段和,以及这些量的端点。合并左右儿子时:
- 区间和直接相加;
- 最大前缀和取“左儿子的最大前缀和”与“左儿子区间和加右儿子最大前缀和”的较大值;
- 最大后缀和对称;
- 最大子段和取左儿子最大子段和、右儿子最大子段和、左儿子最大后缀和加右儿子最大前缀和三者中的最大值。
为了支持区间取反,还要同时维护最小前缀和、最小后缀和、最小子段和及其端点。取反后最大值和最小值互换,再整体取相反数。
区间覆盖时,按区间长度和 的符号重算上述最大/最小字段,并记录覆盖标记。覆盖标记下传时直接覆盖左右儿子,并清空取反标记。
k>1
反复执行至多 次:
- 查询 的最大子段和及其左右端点;
- 若最大子段和小于等于 ,停止;
- 把该和加入答案,并把该子段整体取反;
- 记录这个子段。
询问结束后,把所有记录的子段再取反一次,恢复原序列。每个询问互相独立,不能保留上一次询问的取反结果。
正确性
把序列建成一条单位容量的费用流网络:选择若干不相交子段相当于发送若干单位流量,每单位流量的费用是被选元素之和。每次在残量网络中增广一条最大费用路径,等价于在当前序列中取最大子段;把该子段取反,就是加入反向边。
因此,反复取最大子段并取反,就是在依次做最多 次最大费用增广。若当前最大子段和非正,继续增广不会增加答案,可以停止。最终得到的就是至多 个不相交子段的最大和。
复杂度
建树为 ;单次区间覆盖为 ;单次询问做至多 次查询和取反,每次 ,共 。空间为 。
参考
- 单点修改版本:CF280D k-Maximum Subsequence Sum。