题解 P2048 【[NOI2010]超级钢琴】
这题可以直接用线段树+堆
-
首先处理前缀和
s ，再用线段树维护两个值，分别为区间的最小s[i] 和以及所在的位置(即i )。 -
然后有点类似于
P1631 那样，把以i 结尾的区间中的最大区间和、、以i结尾区间中的首位位置的范围[L,R] ( 因为题目中有区间长度限制) 扔进一个大根堆中。我们只要用s[i] 减去之前最小的前缀和（ 用线段树求最小值） 就能得出以i 结尾的区间中的最大区间和。（ 因为每个区间[l,r] 的值都能写成s[r]-s[l-1] ,当r 为定值时，那么就要使s[r]-s[l-1] 值最大，也就是求s[l-1] 的最小值。) -
最后每次取出堆顶（即堆中区间和最大的那一个），并找出