bzoj 2006. [NOI2010]超级钢琴 题解
Description
给定一个长度为 $n$ 的序列，选出 $k$ 个长度在 $[L,R]$ 之间的子段（不可重复），求 $k$ 个子段和的最大值。
$N\leq 500,000,k\leq 500,000,-1000\leq A_i \leq 1000,1\leq L\leq R\leq N$
Solution
由于 $n$ 十分巨大，我们不可能把所有符合条件的子段都列举出来再比较她们的大小，由于 $k$ 比较小，于是我们需要考虑如何贪心选择最大满足的子段，选择 $k$ 次即是答案。
定义 $f(i,l,r)$ 表示以 $i$ 为右端点，左端点在 $[L,R]$ 区间内的最大子段和，${sum}_i$ 表示前缀和。那么显然可知：
$$f(i,l,r)=\max\