[BZOJ2006] [NOI2010]超级钢琴

本文主要是介绍[BZOJ2006] [NOI2010]超级钢琴，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[BZOJ2006] [NOI2010]超级钢琴

题目大意

给定一个序列,要求找到连续的序列满足长度在$[L,R]$范围内,询问前$k$大的满足条件的序列的和
$n,k\le 5*10^5$

题解

设一个三元组$(R,L1,L2)$:表示左端点在$[L1,L2]$内,右端点为R的区间最大值$=sum[R]-\min\{sum[i]\},i\in[L1,L2]$
依次枚举每一个右端点$i$,将三元组$(i,i-R+1,i-L+1)$取出放进大根堆中
都取完后,每次从堆顶取走最大值加入答案,然后将原三元组从最大值的位置处分裂为两个三元组$(i,i-R+1,pos-1)$和$(i,pos+1,i-L+1)$
一共取k次,总复杂度为$O((N+K)logN)$
CODE

这篇关于[BZOJ2006] [NOI2010]超级钢琴的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---