标签为 [优先队列] 的文章

[BZOJ2006]超级钢琴

题目大意 从一个序列中,找出k段连续的子序列,且每个子序列的长度不小于L,不大于R。 一个序列的权值定义为序列中所有数的和,求k个子序列和的最大值。具体看原题。 Solution 这道题应该用主席树来做,但是太麻烦。相比起来,ST表+堆的算法显然比较方便(可能我代码写得太丑)。 考虑每次取出一段最大的合法的子序列,这样取k次。第一次取的时候,如果枚举了一个右端点r,那么r-R+1<=l<=r-L+1。 如果用前缀和sum数组表示这个区间的和,就是sum[r]-sum[l-1]。当r固定时,l也在一个固定的区间内变化,只要sum[l]取这个区间中的 ......