记录编号	112481	评测结果	WWAWWWWWWW
题目名称	468.[NOI 2010]超级钢琴	最终得分	10
用户昵称	天一阁	是否通过	未通过
代码语言	C++	运行时间	0.966 s
提交时间	2014-07-16 09:22:27	内存使用	40.37 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

const int MAX_N = 500010;

using namespace std;

int rpos[20][MAX_N];
int s[MAX_N],n,K;

struct Node{	//线段树 
	long long num; int l,r,i;
	bool operator<(const Node &a)const{
		return num<a.num;
	}
};

void rmq_init()
{
	int k=0;
	for(;(1<<k+1)<n+1;++k);
	for(int i=0;i<=n;++i) rpos[0][i]=i;
	for(int j=1;j<=k;++j)
	{
		for(int i=0;i+(1<<j)-1<=n;i++)
		{
			int p=rpos[j-1][i],q=rpos[j-1][i+(1<<j-1)];		//更新最大值的坐标 
			rpos[j][i]= s[p]<s[q] ? p:q;
		}
	}
}

int rmq(int l,int r)
{
	int z=r-l+1,k=0;
	for(;(1<<k+1)<z;++k);   //计算层数
	
	int p=rpos[k][l],q=rpos[k][r-(1<<k)+1];
	
	return s[p]<s[q] ? p:q;
}

priority_queue<Node> Q;

void init()
{
	freopen("piano.in","r",stdin);
	freopen("piano.out","w",stdout);
	
	long long ans=0;
	int l,r;
	
	scanf("%d%d%d%d",&n,&K,&l,&r);
	
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		s[i]=s[i-1]+x;
	}
	
	rmq_init();
	
	for(int i=1;i<=n;++i)
	{
		int a=i-r,b=i-l;
		
		if(a<0) a=0;
		if(b>=0) Q.push((Node){s[i]-s[rmq(a,b)],a,b,i});
	}
	
	for(int i=1;i<=K;i++)
	{
		if(Q.empty()) break;
		else
		{
			Node x=Q.top(); Q.pop();
			ans+=x.num;
			
			int t=rmq(x.l,x.r);
			
			if(x.l<=t-1) Q.push((Node){s[x.i]-s[rmq(x.l,t-1)-1],x.l,t-1,x.i}); 
			if(t+1<=x.r) Q.push((Node){s[x.i]-s[rmq(t+1,x.r)-1],t+1,x.r,x.i});
		}
	}
	
	printf("%d\n",ans);
}

int main()
{
	init();
	
	return 0;
}