记录编号	430739	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]超级钢琴	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	0.966 s
提交时间	2017-07-30 16:04:13	内存使用	33.82 MiB

#include<cstdio>
#include<queue>
#define syy myson
using namespace std;
const int maxn=500001;
struct Node
{
	int r,L,R,val;
	Node(){}
	Node(int a,int b,int c,int d)
	{
		r=a;L=b;R=c;val=d;
	}
	bool operator <(const Node &B)const
	{
		return val<B.val;
	}
};
priority_queue<Node>q;
int n,k,low,hi;
int a[maxn],qlog[maxn],st[maxn][20];
void init_st()
{
	for(int i=1;i<=n;i++)st[i][0]=i-1;
	for(int j=1;(1<<j)<=n;j++)
	  for(int i=1;i<=n;i++)
	  {
	  	st[i][j]=st[i][j-1];
	  	if(i+(1<<j-1)<=n&&a[st[i+(1<<j-1)][j-1]]<a[st[i][j]])
	  		st[i][j]=st[i+(1<<j-1)][j-1];
	  }
	for(int j=0;(1<<j)<=n;j++)qlog[1<<j]=j;
	for(int i=3;i<=n;i++)if(qlog[i]==0)qlog[i]=qlog[i-1];
}
int Min(int x,int y)
{
	return a[x]<a[y]?x:y;
}
int qmin(int a,int b)
{
	int j=qlog[b-a+1];
	return Min(st[a][j],st[b-(1<<j)+1][j])+1;
}
int Main()
{
	freopen("piano.in","r",stdin);freopen("piano.out","w",stdout);
	scanf("%d%d%d%d",&n,&k,&low,&hi);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	for(int i=1;i<=n;i++)a[i]+=a[i-1];
	init_st();
	for(int i=1;i<=n;i++)
	{
		if(i>=low)
		{
			int l=max(1,i-hi+1),r=i-low+1;
			q.push(Node(i,l,r,a[i]-a[qmin(l,r)-1]));
		}
	}
	long long ans=0;
	while(k--)
	{
		Node tmp=q.top();q.pop();
		ans=ans+tmp.val;
		int pos=qmin(tmp.L,tmp.R);
		if(pos>tmp.L)
			q.push(Node(tmp.r,tmp.L,pos-1,a[tmp.r]-a[qmin(tmp.L,pos-1)-1]));
		if(pos<tmp.R)
			q.push(Node(tmp.r,pos+1,tmp.R,a[tmp.r]-a[qmin(pos+1,tmp.R)-1]));
	}
	printf("%lld\n",ans);
	return 0;
}
int main(){;}
int syy=Main();
/*
10 13 3 7
595
384
-435
-197
-677
661
4
-100
-653
220
*/