记录编号	484387	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]超级钢琴	最终得分	100
用户昵称	xzz_666	是否通过	通过
代码语言	C++	运行时间	0.724 s
提交时间	2018-01-23 17:58:55	内存使用	36.32 MiB

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
#define rg register
#define vd void
#define sta static
#define il inline
il int gi(){
    rg int x=0,f=1;rg char ch=getchar();
    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int maxn=500002;
int A[maxn],st[19][maxn],log[maxn];
il int orz(rg int x,rg int y){return A[x]<A[y]?x:y;}
il int query(rg int l,rg int r){
	rg int p=log[r-l+1];
	return orz(st[p][l],st[p][r-(1<<p)+1]);
}
struct yyb{int key,r,ll,lr;};
bool operator <(const yyb&a,const yyb&b){return a.key<b.key;}
priority_queue<yyb>que;
main(){
	freopen("piano.in","r",stdin);
	freopen("piano.out","w",stdout);
	int n=gi(),tjj=gi(),L=gi(),R=gi();
	for(rg int i=1;i<=n;++i)A[i+1]=gi(),st[0][i]=i;
	++n,st[0][n]=n;
	for(rg int i=1;i<=n;++i)A[i]+=A[i-1];
	for(rg int i=1;i<=n;++i){
		log[i]=log[i-1];
		if((1<<(log[i]+1))==i)++log[i];
	}
	for(rg int i=1;i<=log[n];++i)
		for(rg int j=n-(1<<i)+1;j;--j)
			st[i][j]=orz(st[i-1][j],st[i-1][j+(1<<(i-1))]);
	for(rg int i=1;i<=n;++i)if(i>L)que.push((yyb){A[i]-A[query(max(1,i-R),i-L)],i,max(1,i-R),i-L});
	long long ans=0;
	yyb x;int k,r,ll,lr;
	while(tjj--){
		x=que.top();que.pop();
		r=x.r,ll=x.ll,lr=x.lr;
		ans+=x.key;k=query(ll,lr);
		if(ll<=k-1)que.push((yyb){A[r]-A[query(ll,k-1)],r,ll,k-1});
		if(k+1<=lr)que.push((yyb){A[r]-A[query(k+1,lr)],r,k+1,lr});
	}printf("%lld\n",ans);
	return 0;
}