BZOJ 2006 [NOI2010] 超级钢琴

发布于 2017-09-18  202 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2006

题意:选出 k 个不同连续子序列,满足这些子序列的和的和最大。


五元组 (sum,x,l,r,id) 表示目前左端点为 x,右端点在 [l,r] 区间内,最大子序列和为 sum,在下标 id 处取到。

用一个堆维护,区间最值处理前缀和后可以 st 表求。

每次取出堆顶,分裂成 [l,id-1],[id+1,r] 两个区间

 


一个非常弱的准退役OIER