题意：
一个序列，求k个不相同的长度属于$[L,R]$的区间使得和最大

---

前缀和，对于每个r找最小的a[l]

然后我yy了一个可持久化线段树做法...也许会T

实际上主席树就可以了，区间k小值

然后看hzwer题解发现还有更有趣的做法，差一点就想到了

\((l,r,x)\)表示左端点在\([l,r]\),右端点为\(x\)的最大和

用优先队列维护

取出\((l,r,x)\)后，区间被分成两段，再加入就行了

MD我连ST表都写错

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int N=5e5+5, INF=1e9;

#define pii pair<int, int>

#define MP make_pair

#define fir first

#define sec second

typedef long long ll;

inline int read(){

	char c=getchar();int x=0,f=1;

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

int n, k, L, R, a[N], Log[N];

struct meow{

	int x, l, r; pii v;

	bool operator <(const meow &a) const {return v < a.v;}

	meow(){}

	meow(int a, int b, int c, pii d):x(a), l(b), r(c), v(d){}

};

priority_queue<meow> q;

pii f[N][21], t;

void ini() {

	for(int i=0; i<=n; i++) f[i][0] = MP(a[i], i);

	for(int i=n; i>=0; i--)

		for(int j=1; i + (1<<j) -1 <=n; j++)

			f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]);// printf("f %d %d %d\n",i,j,f[i][j].fir);

}

inline pii Min(int x, int y) {

	int t = Log[y-x+1]; //printf("\nMin %d %d  %d\n",x,y, t);

	return min(f[x][t], f[y - (1<<t) + 1][t]);

}

int main() {

	freopen("in","r",stdin);

	n=read(); k=read(); L=read(); R=read();

	Log[1] = 0;

	for(int i=2; i<=n; i++) Log[i] = Log[i>>1] + 1;

	for(int i=1; i<=n; i++) a[i] = read()+a[i-1];

	ini();

	for(int i=L; i<=n; i++) {

		int l = max(0, i-R), r = i-L;

		t=Min(l, r);

		q.push(meow(i, l, r, MP(a[i] - t.fir, t.sec) ));

	}

	ll ans=0;

	while(k--) {

		meow now = q.top(); q.pop();

		ans += now.v.fir;

		int x = now.x, l = now.l, r = now.r, p = now.v.sec;

		if(l < p) t=Min(l, p-1), q.push(meow(x, l, p-1, MP(a[x] - t.fir, t.sec) ));

		if(p < r) t=Min(p+1, r), q.push(meow(x, p+1, r, MP(a[x] - t.fir, t.sec) ));

	}

	printf("%lld", ans);

}