记录编号	484584	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]超级钢琴	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	2.092 s
提交时间	2018-01-25 15:42:34	内存使用	33.82 MiB

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1e9
using namespace std;
const int maxn=500010;
struct tree{int l,r,place;long long maxx;}t,tr[maxn*4];
struct poi{long long w;int l,r,id,place;};
priority_queue<poi>q;
bool operator < (poi x,poi y){return x.w<y.w;}
int n,k,L,R;
long long ans,a[maxn];
void build(int x,int l,int r){
	tr[x].l=l,tr[x].r=r;
	if(l==r){tr[x].maxx=a[l],tr[x].place=l;return;}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	tr[x].maxx=max(tr[x<<1].maxx,tr[x<<1|1].maxx);
	if(tr[x<<1].maxx>tr[x<<1|1].maxx)tr[x].place=tr[x<<1].place;
	else tr[x].place=tr[x<<1|1].place;
}
tree ask(int x,int l,int r){
	tree tmp1,tmp2;
	tmp1.maxx=tmp2.maxx=-(long long)inf,tmp1.place=tmp2.place=0;
	if(l<=tr[x].l&&tr[x].r<=r)return tr[x];
	if(l<=tr[x<<1].r)tmp1=ask(x<<1,l,r);
	if(r>=tr[x<<1|1].l)tmp2=ask(x<<1|1,l,r);
	if(tmp1.maxx<tmp2.maxx)return tmp2;
	else return tmp1;
}
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("%lld",&a[i]),a[i]+=a[i-1];
	build(1,1,n);
	for(int i=1;i<=n-L+1;i++){
		int l=i+L-1,r=min(i+R-1,n);
		t=ask(1,l,r);
		q.push((poi){t.maxx-a[i-1],l,r,i,t.place});
	}
	poi tmp;
	while(k--){
		tmp=q.top();q.pop();
		ans+=tmp.w;
		if(tmp.place-1>=tmp.l){
			t=ask(1,tmp.l,tmp.place-1);
			q.push((poi){t.maxx-a[tmp.id-1],tmp.l,tmp.place-1,tmp.id,t.place});
		}
		if(tmp.place+1<=tmp.r){
			t=ask(1,tmp.place+1,tmp.r);
			q.push((poi){t.maxx-a[tmp.id-1],tmp.place+1,tmp.r,tmp.id,t.place});
		}
	}
	printf("%lld\n",ans);
	return 0;
}