记录编号	60518	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]超级钢琴	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	3.171 s
提交时间	2013-05-26 11:58:15	内存使用	75.82 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<queue>
#include<deque>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const ll SIZEN=500010;
ll n,k;
ll a[SIZEN]={0};
ll s[SIZEN]={0};
ll f[SIZEN][20]={0};//ST,但里面存的是最大值的位置
ll min(ll a,ll b){
	return a<b?a:b;
}
void ST_init(ll a[SIZEN]){
	ll m=floor(log((double)n)/log(2.0));
	ll i,j;
	for(i=1;i<=n;i++) f[i][0]=i;
	for(j=1;j<=m;j++){
		for(i=1;i<=n;i++){
			if(i+(1<<j)-1>n) continue;
			f[i][j]=f[i][j-1];
			if(a[f[i+(1<<(j-1))][j-1]]>a[f[i][j]]) f[i][j]=f[i+(1<<(j-1))][j-1];
		}
	}
}
ll rmq(ll l,ll r){//这里返回的是位置
	ll m=floor(log((double)(r-l+1))/log(2.0));
	if(s[f[l][m]]>s[f[r-(1<<m)+1][m]]) return f[l][m];
	else return f[r-(1<<m)+1][m];
}
class NODE{
public:
	ll pos;
	ll l,r;
	ll num;
	//这样四个数表示:在左端点为pos,右端点在[l,r]之间的所有和弦的最大值num
	ll ind;//最大值的标号
	void calc(void){
		ind=rmq(l,r);
		num=s[ind]-s[pos-1];
	}
};
bool operator < (NODE a,NODE b){
	return a.num<b.num;
}
priority_queue<NODE> Q;
ll ans=0;
void work(void){
	ll i;
	NODE x,y,z;
	for(i=1;i<=k;i++){
		x=Q.top();Q.pop();
		ans+=x.num;
		y.pos=z.pos=x.pos;
		y.l=x.l,z.r=x.r;
		y.r=x.ind-1,z.l=x.ind+1;
		if(y.r>=y.l){
			y.calc();
			Q.push(y);
		}
		if(z.r>=z.l){
			z.calc();
			Q.push(z);
		}
	}
}
void init(void){
	ll L,R;
	scanf("%lld%lld%lld%lld",&n,&k,&L,&R);
	ll i;
	for(i=1;i<=n;i++){
		scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
	}
	ST_init(s);
	NODE x;
	ll lnow,rnow;
	for(i=1;i<=n;i++){
		if(i+L-1>n) break;
		lnow=i+L-1;
		rnow=min(i+R-1,n);
		x.pos=i,x.l=lnow,x.r=rnow;
		x.calc();
		Q.push(x);
	}
}
int main(){
	freopen("piano.in","r",stdin);
	freopen("piano.out","w",stdout);
	init();
	work();
	cout<<ans<<endl;
	return 0;
}