●BZOJ 2006 NOI 2010 超级钢琴

题链：

题解：

RMQ + 优先队列 （+ 前缀）

记得在一两个月前，一次考试考了这个题目的简化版：序列中只有正整数。
当时我们曰 ：有负数的话就怕是莫得解法哦。
然后，有负数的情况居然是NOI题。。。
难哭。

1).首先尝试固定区间的右端点R。
那么可取的左端点的范围就已经确定。
所以对于右端点为 R的权和最大的区间就能够求出来了：
先求出前缀序列 pre[]，
由于 sum = pre[R]-pre[L-1],且 pre[R] 固定，
即我们需要求出合法范围内的最小的 pre[L-1],
这个就可以用 RMQ实现。

2).用优先队列维护。
初始化时，把每个右端点R的最大权和区间的相关信息放入队列：
保存这些信息 ：
{sum(该区间的和),R(固定的区间右端点是谁),p(区间和为sum时对应的左端点),l(左端点的左界),r(左端点的右界)}
那么直接取堆顶，即是当前的最大权和区间。
然后接下呢，为了以后不重复取到当前区间，我们把 [l,r] 剖成 [l,p-1] 和 [p+1,r]
并计算出相应的信息，继续放入优先队列，即把
{sum1,R,p1,l,p-1} 和  {sum2,R,p2,p+1,r} 加入进去。
重复操作 K次即可。

代码：

#include
#include
#include
#include
#define MAXN 500005
#define ll long long
using namespace std;
struct info{
	ll sum,R,p,l,r;
	bool operator <(const info & rtm) const{
		return sumq;
ll query(ll l,ll r){
	static ll k,mini;
	k=log2[r-l+1];
	mini=min(stv[l+(1<>1]+1;
	scanf("%lld%lld%lld%lld",&N,&K,&A,&B);
	for(ll i=1;i<=N;i++)
		scanf("%lld",&pre[i]),pre[i]+=pre[i-1],stv[i][0]=pre[i],stp[i][0]=i;
	for(ll k=1;k<=log2[N];k++)
		for(ll i=(1<=now.l){ 
			pos=query(now.l-1,now.p-1-1)+1; 
			q.push((info){pre[now.R]-pre[pos-1],now.R,pos,now.l,now.p-1});
		} 
		if(now.r>=now.p+1){
			pos=query(now.p+1-1,now.r-1)+1;
			q.push((info){pre[now.R]-pre[pos-1],now.R,pos,now.p+1,now.r});
		}
	}
	printf("%lld",ans);
	return 0;
}