记录编号	484699	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]超级钢琴	最终得分	100
用户昵称	泪寒之雪	是否通过	通过
代码语言	C++	运行时间	7.063 s
提交时间	2018-01-26 10:29:30	内存使用	6.60 MiB

#pragma GCC optimize("-O2")
#include<bits/stdc++.h>
#define N 700007
#define rr NULL
using namespace std;
struct Node{
	int key,id;
	Node(){}
	Node(int x,int y):key(x),id(y){}
	inline bool operator <(const Node A)const {
	  return A.key^key?key<A.key:id<A.id;
	}
}a[N];
priority_queue<Node> Q;
inline int rop(){
	static int x=23333;
	return x^=x<<13,x^=x>>17,x^=x<<5;
}
#define sight(c) ('0'<=c&&c<='9')
inline void read(int &x){
    static char c;static int b;
    for (b=1,c=getchar();!sight(c);c=getchar())if (c=='-') b=-1;
    for (x=0;sight(c);c=getchar())x=x*10+c-48; x*=b;
}
struct T{
	int val,siz; Node key;
    T* son[2];
    T() {}
    T(Node x){
    	key=x;val=rop(),siz=1;
    	son[0]=son[1]=rr;}
    void red(){
    	siz=1; 
    	if (son[0]) siz+=son[0]->siz;
    	if (son[1]) siz+=son[1]->siz;
	}
	int ibt(){return son[0]?son[0]->siz+1:1;}
};
int Kth(Node x,T* now){
	if (!now) return 0;
	if (now->key<x) return now->ibt()+Kth(x,now->son[1]);
	return Kth(x,now->son[0]);
}
void split(T* now,int k,T*& x,T*& y){
	if (!now) {x=y=rr;return;}
	int cmp=now->ibt();
	if (k<cmp) y=new T(),*y=*now,split(y->son[0],k,x,y->son[0]),y->red();
	else x=new T(),*x=*now,split(x->son[1],k-cmp,x->son[1],y),x->red();
}
void Split(T* now,int k,T*& x,T*& y){
	if (!now) {x=y=rr;return;}
	int cmp=now->ibt();
	if (k<cmp) y=now,Split(y->son[0],k,x,y->son[0]),y->red();
	else x=now,Split(x->son[1],k-cmp,x->son[1],y),x->red();
}
T* merge(T* x,T* y){
	if (!x) return y; if (!y) return x;
	if (x->val<y->val) {
	T* X=new T();*X=*x;
	X->son[1]=merge(X->son[1],y);X->red();return X;}
	T* X=new T();*X=*y;
	X->son[0]=merge(x,X->son[0]);X->red(); return X;
}
T* Merge(T* x,T* y){
	if (!x) return y; if (!y) return x;
	if (x->val<y->val) {x->son[1]=Merge(x->son[1],y);x->red();return x;}
	y->son[0]=Merge(x,y->son[0]);y->red();return y;
}
int n,k,l,r,XX,in[N],h,K;
T* rt[N],*x,*y,*z,*t;
long long ans;
Node X;
void dfs(T* x){
	if (!x) return;
	dfs(x->son[0]);
	cerr<<x->key.key<<' ';
	dfs(x->son[1]);
}
int main() {
	freopen("piano.in","r",stdin);
	freopen("piano.out","w",stdout);
	read(n); read(K); read(l); read(r);
	for (int i=1;i<=n;i++) read(XX),
	a[i].key=a[i-1].key+XX,a[i].id=i;
	for (int i=l;i<=r;i++) {
		k=Kth(a[i],rt[1]); Split(rt[1],k,x,y);
		rt[1]=Merge(Merge(x,new T(a[i])),y);
	} 
	for (int i=l+1,j=r+1;i<=n;i++,j++) {
		k=Kth(a[i-1],rt[i-l]); 
		split(rt[i-l],k,x,y);
		split(y,1,t,y); rt[i-l+1]=Merge(x,y);
		if (j>n) continue;
		k=Kth(a[j],rt[i-l+1]); 
		split(rt[i-l+1],k,x,y);
		rt[i-l+1]=Merge(x,Merge(new T(a[j]),y));
	}
	for (int i=l,j=r;i<=n;i++,j++) {
		Split(rt[i-l+1],rt[i-l+1]->siz-1,x,y);
		Q.push(Node(y->key.key-a[i-l].key,i)); 
		rt[i-l+1]=Merge(x,y); 
		in[i]=1;
	}
	while (K--) {
		X=Q.top();Q.pop(); 
		ans+=X.key; h=X.id;
		if (in[h]>=rt[h-l+1]->siz) continue;
		Split(rt[h-l+1],rt[h-l+1]->siz-1-in[h],x,z); Split(z,1,y,z);
		Q.push(Node(y->key.key-a[h-l].key,h));
		rt[h-l+1]=Merge(x,Merge(y,z));
		in[h]++;
	}
	printf("%lld\n",ans);
}