第k小子序列和与第k大子段和

第 $k$ 小子序列和

先把所有数从小到大排序.
设一个二元组 $(sum, i)$ , 表示以第 $i$ 位为结尾, 和为 $sum$ 的子序列, 建一个小根堆来维护这些二元组, 每次取出堆顶, 然后把 $(sum + a_{i + 1}, i + 1)$ 和 $(sum + a_{i+1} - a_i, i + 1)$ 加入堆中, 即把第 $i+1$ 个数加入到序列中, 或把序列中最大的数替换成第 $i+1$ 个数. 显然这样可以不重不漏地按顺序遍历完所有情况.

然后第 $k$ 个被取出堆顶的数就是答案.

例题

第 $k$ 大子段和.

设一个三元组 $(o, l, r)$ 表示左端点位置是 $o$, 右端点在 $[l,r]$ 的子段, 定义这个三元组的值为这些子段和的最大值, 即 $\max_{i=l}^{r} (sum_i - sum_{o - 1}) = \max_{i=l}^{r} (sum_i ) - sum_{o - 1}$, 用大根堆来维护, 如果从堆顶取出的是 $(o, l, r)$ , 那么找出最大的 $sum_x$ , 既然已经选了左端点为 $o$, 右端点为 $x$ 的子段, 那么就把三元组一分为二, 分成 $(o, l, x - 1)$ 和 $(o, x + 1, r)$

然后第 $k$ 个被取出堆顶的数就是答案.

例题 题解

总结

这两类问题都灵活的运用了堆, 所以可以总结出求第 $k$ 大的一种方法:
把当前有的情况放到堆中, 每次从堆中取出堆顶, 并拓展出其它情况放入堆中. 这样重复 $k$ 次.
但前提是用这种方法必须要 能够 不重不漏地按顺序遍历完所有情况, 即第 $k$ 次从堆顶取出的值必须是第 $k$ 大值(或第 $k$ 小值).