题目大意：求序列内长度在$[L,R]$范围内前$k$大子序列之和。
----------------------
考略每个左端点$i$，合法的区间右端点在$[i+L,i+R]$内。
不妨暴力枚举所有左端点，找到以其为左端点满足条件的最大子序列。
用贪心的思想，这些序列一定是满足题意的。统计后将该序列删除。
但这样直接删除肯定会丢失一部分有用的序列。一些也在前$k$大范围内的序列可能跟删除部分有交集。
所以我们不妨设$maxi$指以$i$为左端点的子序列，以$maxi$为右端点时能取得最大值。从此处将原先的大区间$[i+L,i+R]$裂解成两个区间$[i+L，maxi-1]$和$[maxi+1,i+R]$。从这两个区间中再找较大的满足条件的序列。
维护显然用堆。设一个五元组$(v,i,l,r,w)$表示以$i$为左端点，右端点在$[i+L,i+R]$内时，能找出以$w$为右端点的最大值为$v$的子序列。以$v$作为关键字，建立大根堆维护即可。
最后一个问题就是查找。我们不妨预处理出前缀和，用前缀和查找子序列的和。最大值用$ST$表维护。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005;
int f[N][21],pos[N][21];
int n,k,l,r,op;
long long ans;
int maxn,maxi;
struct node
{
int v,i,l,r,w;
}t,tmp;
bool operator <(const node &a,const node &b)
{
return a.v<b.v;
}
priority_queue<node> q;
inline void RMQ(int l,int r)
{
int opt=log2(r-l+1);
if (f[l][opt]>=f[r-(1<<opt)+1][opt]) maxn=f[l][opt],maxi=pos[l][opt];
else maxn=f[r-(1<<opt)+1][opt],maxi=pos[r-(1<<opt)+1][opt];
}
signed main()
{
memset(f,128,sizeof(f));
f[0][0]=0;
scanf("%lld%lld%lld%lld",&n,&k,&l,&r);
op=log2(n);
for (int i=1;i<=n;i++)
{
scanf("%lld",&f[i][0]);
pos[i][0]=i;
f[i][0]+=f[i-1][0];
}
for (int t=1;t<=op;t++)
for (int i=1;i<=n;i++) if (i+(1<<(t-1))-1>n) break;
else
{
if (f[i][t-1]>=f[i+(1<<(t-1))][t-1]) f[i][t]=f[i][t-1],pos[i][t]=pos[i][t-1];
else f[i][t]=f[i+(1<<(t-1))][t-1],pos[i][t]=pos[i+(1<<(t-1))][t-1];
}
for (int i=1;i<=n-l+1;i++)
{
RMQ(i+l-1,i+min(n-i,r-1));
t.v=maxn-f[i-1][0],t.i=i,t.l=i+l-1,t.r=i+min(n-i,r-1),t.w=maxi;
q.push(t);
}
while(k--)
{
t=q.top();
q.pop();
ans+=t.v;
if (t.w>t.l)
{
RMQ(t.l,t.w-1);
tmp.v=maxn-f[t.i-1][0],tmp.i=t.i,tmp.l=t.l,tmp.r=t.w-1,tmp.w=maxi;
q.push(tmp);
}
if (t.w<t.r)
{
RMQ(t.w+1,t.r);
tmp.v=maxn-f[t.i-1][0],tmp.i=t.i,tmp.l=t.w+1,tmp.r=t.r,tmp.w=maxi;
q.push(tmp);
}
}
printf("%lld",ans);
return 0;
}