题解

思路

小规模可以枚举选取集合，中档数据可以按查询做动态规划；满分做法把“选择至多 $k$ 段”转化为至多 $k$ 次最大子段增广，并用支持区间取反的线段树维护。

做法

子任务 1

枚举查询区间中每个位置选或不选。被选位置的连续块数不超过 $k$ 时，用所选元素之和更新答案。复杂度为 $O(2^{r-l+1})$。

子任务 2

设 local[j] 表示当前正在第 $j$ 个被选子段内的最大和，global[j] 表示已经使用不超过 $j$ 段的最大和。扫描区间元素 $x$ 时：

$$local_j\leftarrow\max(local_j,global_{j-1})+x, \qquad global_j\leftarrow\max(global_j,local_j).$$

每次查询复杂度 $O((r-l+1)k)$。

子任务 3

线段树结点同时维护区间和、最大与最小前缀、后缀和子段，并记录最值子段的端点。区间整体乘 $-1$ 时，最大值与最小值互换并取相反数，因此可懒标记维护区间取反。

对一次查询，反复取当前最大子段：若其和非正则停止；否则把它加入答案，并将该子段取反。这个过程等价于在“至多若干个不相交子段”的选择上进行一次增广：取反既能加入一个新段，也能通过下一次最大子段跨越负区间来合并、拆分已有选择。重复至多 $k$ 次后得到最优答案。最后把本次取反的区间全部再取反一次，恢复原序列。

点修改直接在线段树中单点赋值。

正确性

中档动态规划显式枚举每个位置是否属于当前段，覆盖所有至多 $k$ 段的选择。满分算法中，每次最大子段查询给出当前选择与增加一个段后的最大增广量；区间取反恰好维护已选边与未选边的增广权值。若最大增广量不为正，继续增加段不会改善答案；否则加入该增广量保持最优。归纳可得第 $j$ 次后答案等于至多 $j$ 段的最优值。

复杂度

• 子任务 1：单次查询 $O(2^{r-l+1})$；
• 子任务 2：单次查询 $O((r-l+1)k)$；
• 子任务 3：修改 $O(\log n)$，查询 $O(k\log n)$，空间 $O(n)$。