大致题意
找出 \(k\) 个 不完全相同 的长度为 \(L-R\) 的区间，使其区间和最大。
题解
区间和，首先想前缀和维护；区间长度有范围，可以用 st表 维护区间最值优化。
因为要求不完全相同，开结构体记录区间端点。
假如以 \(i\) 为起点，\(t\) 为 \(i+L-1--i+R-1\) 中最优值，找到 \(i-t\) 区间和最大，因为只要求 不完全相同，
所以次大值可能出现在 \(i-(t-1)\) 或 \(i-(t+1)\) 中，要注意。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 500005;
int n,a[N],k,L,R,st[N][40];long long sum[N];
int que(int l,int r)
{
int k=log2(r-l+1);
if(sum[st[l][k]]>sum[st[r-(1<<k)+1][k]])
return st[l][k];
else return st[r-(1<<k)+1][k];
}
bool cmp(int x,int y)
{
return x>y;
}
struct A
{
int o,l,r,t;
bool operator < (const A &x) const
{
return sum[t]-sum[o-1]<sum[x.t]-sum[x.o-1];
}
};
int main()
{
priority_queue<A> q;
scanf("%d%d%d%d",&n,&k,&L,&R);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
st[i][0]=i;
}
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
{
if(sum[st[j][i-1]]>sum[st[j+(1<<(i-1))][i-1]])
st[j][i]=st[j][i-1];
else
st[j][i]=st[j+(1<<(i-1))][i-1];
}
for(int i=1;i+L-1<=n;i++)
{
int x=i+L-1,y=min(i+R-1,n);
q.push(A{i,x,y,que(x,y)});
}
long long ans=0;
for(int i=1;i<=k;i++)
{
int l=q.top().l,o=q.top().o,r=q.top().r,t=q.top().t;
q.pop();
ans+=sum[t]-sum[o-1];
if(l!=t) q.push(A{o,l,t-1,que(l,t-1)});
if(t!=r) q.push(A{o,t+1,r,que(t+1,r)});
}
printf("%lld\n",ans);
return 0;
}