记录编号	241205	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]超级钢琴	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	6.522 s
提交时间	2016-03-24 19:33:28	内存使用	113.77 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=500010;
int n,K,L,R,s[maxn],pos;
struct Node{
	int node,l,r;
	Node(int NODE=0,int L=0,int R=0){
		node=NODE;l=L;r=R;
	}
};
int mm[maxn],Max[maxn][25],Mpos[maxn][25];

int Query(int l,int r){
	if(Max[l][mm[r-l+1]]<Max[r-(1<<mm[r-l+1])+1][mm[r-l+1]]){
		pos=Mpos[r-(1<<mm[r-l+1])+1][mm[r-l+1]];
		return Max[r-(1<<mm[r-l+1])+1][mm[r-l+1]];
	}
	else{
		pos=Mpos[l][mm[r-l+1]];
		return Max[l][mm[r-l+1]];
	}
}

int Q(Node x){
	return Query(x.l,x.r)-s[x.node-1];
}

struct Heap{
	int cnt;
	Node h[maxn<<1];
	void Insert(Node x){
		int p=++cnt;
		while(p!=1){
			if(Q(x)<=Q(h[p>>1]))break;
			h[p]=h[p>>1];
			p>>=1;
		}
		h[p]=x;
	} 
	
	void Delete(){
		int p=1,a,b;
		Node x=h[cnt--];
		while(p*2<=cnt){
			a=p<<1;b=a|1;
			if(b<=cnt&&Q(h[a])<Q(h[b]))a=b;
			if(Q(h[a])<=Q(x))break;
			h[p]=h[a];
			p=a;	
		}
		h[p]=x;
	}
}q;

int main(){
	freopen("piano.in","r",stdin);
	freopen("piano.out","w",stdout);
	scanf("%d%d%d%d",&n,&K,&L,&R);
	
	for(int i=1;i<=n;i++)
		scanf("%d",&s[i]);	
	for(int i=1;i<=n;i++)
		s[i]+=s[i-1];
	
	mm[0]=-1;
	for(int i=1;i<=n;i++){
		mm[i]=(i&(i-1))==0?mm[i-1]+1:mm[i-1];
		Max[i][0]=s[i];
		Mpos[i][0]=i;
	}
	
	for(int k=1;k<=mm[n];k++)
		for(int i=1;i+(1<<k)-1<=n;i++){
			if(Max[i][k-1]>Max[i+(1<<(k-1))][k-1]){
				Max[i][k]=Max[i][k-1];
				Mpos[i][k]=Mpos[i][k-1];
			}
			else{
				Max[i][k]=Max[i+(1<<(k-1))][k-1];
				Mpos[i][k]=Mpos[i+(1<<(k-1))][k-1];
			}
		}
	
	for(int i=1;i<=n-L+1;i++)
		q.Insert(Node(i,i+L-1,min(i+R-1,n)));
	
	long long ans=0;
	int p;
	Node x;
	while(K--){
		ans+=Q(q.h[1]);
		x=q.h[1];p=pos;
		q.Delete();
		
		if(x.l<p)q.Insert(Node(x.node,x.l,p-1));
		if(x.r>p)q.Insert(Node(x.node,p+1,x.r));
	}
	printf("%lld\n",ans);
	return 0;
}