如果枚举所有的情况肯定是不行的。不过可以发现一些对答案完全没有影响的答案也被枚举，十分浪费时间，所以下面介绍一种很好的思路。
首先，考虑优化暴力（暴力指用堆维护每一个区间的和，然后取堆中前 $m$ 数大记入答案）。为了减少不必要的枚举所以维护一个四元组$(start,l,r,pos)$，$start$ 表示区间左端点，$[l,r]$ 表示区间右端点的范围，$pos$ 表示右端点在$pos$时该区间之和取最大值。如果有多个右端点都能取到最大值，$pos$等于随便一个右端点即可，不会影响到答案。在统计答案的时候每取出一个四元组，就要往堆中加入 $(start,l,pos-1,?)$ 和 $(start,pos+1,r,?)$，注意考虑 $l=pos$ 和 $pos=r$ 的情况。这样的话只需最初枚举每一个 $start$，向堆中加入 $(start,start+l-1,start+r-1,?)$ 即可，枚举次数大幅度减少。
然后考虑如何在确定左端点的情况下找到右端点在 $[l,r]$ 范围内取到最大值时的位置。这很显然是一个RMQ问题，使用ST表维护即可。
标签：RMQ,答案,pos,start,枚举,NOI2010,端点,P2048 From： https://www.cnblogs.com/nebula-xy/p/17032214.html