能过样例，自己造数据也找不出问题，却只能过两个点(#1#4)。

与题解上往下数第三篇思路比较相似（自己写的不是抄的，写完才看到这么像）。

万分感谢调教，蒟蒻写倍增的信息都快被这题击碎了。

//Cuxhin、初心 
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N = 5*1e5+10;//n的最值 
int n,kk,L,R;//分别对应题目n,k,L,R 
ll ans=0;//答案 
ll s[N];//前缀和 
int f[N][25];//st表，存的是坐标（第几个音符） 
class Node{//优先队列的类，区间 
public:
	//注：我这里是半开区间(i,t]，后面同理 
	int i,t,l,r;//以i为起点前一步，s[t]-s[i]最大时的t(前缀和最大)，区间范围l，r 
	Node(){
		
	}
	Node(int a,int b,int c,int d):i(a),l(b),r(c),t(d){//构造函数 
	}
	friend bool operator<(Node a,Node b){//优先队列以值最大排序 
		return (s[a.t]-s[a.i])<(s[b.t]-s[b.i]);
	}
};
priority_queue<Node> q;
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d%d%d%d",&n,&kk,&L,&R);
	for(int i=1;i<=n;i++){
		scanf("%lld",&s[i]);
		s[i]+=s[i-1];//前缀和 
		f[i][0]=i;//初始化st表 
	}
	//st表的构造，以i为起点，长度2^k的区间，[i,i+2^k-1] 
	for(int k=1;(1<<k)<=n;k++){//2^k长度的区间 
		for(int i=1;i+(1<<k)-1<=n;i++){//第i为起点 
			if(s[f[i][k-1]]>=s[f[i+(1<<(k-1))][k-1]]){//2^k分割成2^(k-1)左边区间
				f[i][k]=f[i][k-1]; 
			}
			else{
				f[i][k]=f[i+(1<<(k-1))][k-1];
			}
		}
	}
	//初始化优先队列 
	for(int i=0,k=log2(R-L+1),tR;i+L<=n;i++){
		if(i+R>n){//这里是处理i+R过n的情况，临时修改区间的最大长度，不然会i+R会过n 
			tR=n-i;
			k=log2(tR-L+1);//k只会越改越小 
		}
		else tR=R;//为了方便后面也用tR存R了 
		//查询区间的最值
		if(s[f[i+L][k]]>=s[f[(i+tR)-(1<<k)+1][k]]){ 
			q.push(Node(i,L,tR,f[i+L][k]));
		}
		else{
			q.push(Node(i,L,tR,f[(i+tR)-(1<<k)+1][k]));			
		}
	}
	//输出kk（题目中的k，为了避免冲突双写了）个答案 
	while(kk--){
		Node tmp=q.top();//找队头，区间和最大的 
		q.pop();//弹出 
		int i=tmp.i,l=tmp.l,r=tmp.r,t=tmp.t;//拆开并临时存储队头 
		ans+=(s[t]-s[i]);//加入答案 
		if(t-i!=l){//左边能拆 
			int nr=(t-1)-i,k=log2((nr-l+1));//新的最大区间长度
			//查找新区间最值 
			if(s[f[i+l][k]]>=s[f[(i+nr)-(1<<k)+1][k]]){
				q.push(Node(i,l,nr,f[i+l][k]));
			}
			else{
				q.push(Node(i,l,nr,f[(i+nr)-(1<<k)+1][k]));			
			}
		}
		if(t-i!=r){//右边能拆 
			int nl=(t+1)-i,k=log2(r-nl+1);//新的最短区间长度
			//查找新区间最值 
			if(s[f[i+nl][k]>=s[f[(i+r)-(1<<k)+1][k]]]){
				q.push(Node(i,nl,r,f[i+nl][k]));
			}
			else{
				q.push(Node(i,nl,r,f[(i+r)-(1<<k)+1][k]));
			}
		}
			
	}
	printf("%lld",ans);
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}