记录编号	452012	评测结果	AAAAEAAAEE
题目名称	[NOI 2010]超级钢琴	最终得分	70
用户昵称	JustWB	是否通过	未通过
代码语言	C++	运行时间	6.837 s
提交时间	2017-09-18 20:02:26	内存使用	6.04 MiB

#include<cstdio>
#include<queue>
#include<iostream>
#include<algorithm>
#define mid ((L+R)>>1)
const int maxn=500005;
using namespace std;
struct tuple
{
	long long st,l,r,k,va;
	bool mmp;
	tuple(){st=l=r=k=va=0;mmp=false;}
	bool operator < (const tuple &a)const
	{
		return va<a.va;
	}
};
struct pstree
{
	long long v;
	pstree *ls,*rs;
	pstree(){v=0;ls=rs=NULL;}
}*root[maxn];
inline int get();
pstree *insert(pstree *&now,long long v,long long L,long long R);
int search(pstree *l,pstree *r,long long k,long long L,long long R);
int n,k,z,y;
long long ans;
long long N[maxn],mi=1,mx;
priority_queue<tuple> T;
int main()
{
	freopen("piano.in","r",stdin);
	freopen("piano.out","w",stdout);
	n=get(),k=get(),z=get(),y=get();
	for(int i=1;i<=n;i++)N[i]=N[i-1]+get(),mx=max(mx,N[i]),mi=min(mi,N[i]);
	for(int i=1;i<=n;i++)root[i]=insert(root[i-1],N[i],mi,mx);
	for(int i=n;i>=z;i--)
	{
		register tuple temp;
		temp.st=N[i];
		if(i-y<=0)temp.l=0,temp.r=i-z;
		else temp.l=i-y,temp.r=i-z;
		if(!temp.l)
		{
			int t=search(root[temp.l],root[temp.r],++temp.k,mi,mx);
			if(t<=0)temp.va=temp.st-t;
			else temp.va=temp.st,temp.mmp=true;
		}
		else temp.va=temp.st-search(root[temp.l-1],root[temp.r],++temp.k,mi,mx);
		T.push(temp);
	}
	while(k--)
	{
		ans+=(T.top().va);
		register tuple temp=T.top();
		if(temp.r-temp.l>=temp.k)
		{
			if(!temp.l)
			{
				if(temp.mmp)temp.va=temp.st-search(root[temp.l],root[temp.r],++temp.k-1,mi,mx);
				else
				{
					int t=search(root[temp.l],root[temp.r],++temp.k,mi,mx);
					if(t<=0)temp.va=temp.st-t;
					else temp.va=temp.st,temp.mmp=true;
				}
			}
			else temp.va=temp.st-search(root[temp.l-1],root[temp.r],++temp.k,mi,mx);
			T.pop();
			T.push(temp);
			continue;
		}
		T.pop();
	}
	printf("%lld",ans);
	return 0;
}
int search(pstree *l,pstree *r,long long k,long long L,long long R)
{
	if(L==R)return L;
	if(!l)l=new pstree();
	if(!r)r=new pstree();
	register int temp,a,b;
	if(!l->ls)a=0;
	else a=l->ls->v;
	if(!r->ls)b=0;
	else b=r->ls->v;
	temp=b-a;
	if(k<=temp)return search(l->ls,r->ls,k,L,mid);
	else return search(l->rs,r->rs,k-temp,mid+1,R); 
}
pstree *insert(pstree *&now,long long v,long long L,long long R)
{
	pstree *p=new pstree();
	if(!now)now=new pstree();
	p->v=now->v;
	if(L==R)p->v++;
	else if(v<=mid)
		p->ls=insert(now->ls,v,L,mid),
		p->rs=now->rs;
	else
		p->ls=now->ls,
		p->rs=insert(now->rs,v,mid+1,R);
	if(!p->ls&&p->rs)p->v=p->rs->v;
	else if(p->ls&&!p->rs)p->v=p->ls->v;
	else if(p->ls&&p->rs)p->v=p->ls->v+p->rs->v;
	return p;
}
inline int get()
{
	int t=0;char c=getchar(),j=1;
	while(!isdigit(c))
		if(c=='-')j=-1,c=getchar();
		else c=getchar();
	while(isdigit(c))
		t=(t<<3)+(t<<1)+c-'0',
		c=getchar();
	return j*t;
}