题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=2006

题解：

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<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#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 sum<rtm.sum;

	}

};

ll stv[MAXN][20],stp[MAXN][20],log2[MAXN];

ll pre[MAXN],N,K,A,B,ans;

priority_queue<info>q;

ll query(ll l,ll r){

	static ll k,mini;

	k=log2[r-l+1];

	mini=min(stv[l+(1<<k)-1][k],stv[r][k]);

	if(stv[l+(1<<k)-1][k]==mini) return stp[l+(1<<k)-1][k];

	else return stp[r][k];

}

int main()

{

	freopen("piano.in","r",stdin);

	freopen("piano.out","w",stdout);

	log2[1]=0; ll pos; info now;

	for(ll i=2;i<=MAXN-5;i++) log2[i]=log2[i>>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<<k)-1;i<=N;i++){

			stv[i][k]=min(stv[i][k-1],stv[i-(1<<(k-1))][k-1]);

			if(stv[i][k-1]==stv[i][k]) stp[i][k]=stp[i][k-1];

			else stp[i][k]=stp[i-(1<<(k-1))][k-1];

		}

	for(ll i=1,lmin,lmax;i<=N;i++){

		lmin=max(1ll,i-B+1); lmax=max(0ll,i-A+1);

		if(lmax==0) continue;

		pos=query(lmin-1,lmax-1)+1;

		q.push((info){pre[i]-pre[pos-1],i,pos,lmin,lmax});

	}

	while(K--){

		now=q.top(); q.pop();

		ans+=now.sum;

		if(now.p-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;

}