【题意】给定长度为n的整数序列，求长度为[L,R]的前k大区间和的和。n,k<=500000。
【算法】堆+贪心+RMQ
【题解】考虑暴力是取所有长度为[L,R]的子串的前k大求和，复杂度O(n^2)。
发现左端点相同的区间[l,r]中，最大的区间和就是最大的sum[r]（sum是前缀和数组）。
然后将所以左端点放进堆中，每次取出堆顶之后把第二大的r扔进去，重复k次。
现在的问题是取区间最大的r，第二大的r……区间第k大？用主席树维护即可，复杂度O(n log n)。
还可以用ST表（RMQ）维护，定义三元组(x,l,r)表示取左端点为x，右端点为[l,r]的区间最大sum[r]。
假设对于(x,l,r)，取出元素y，就在堆中加入两个三元组(x,l,y-1)和(x,y+1,r)。
复杂度O(n log n)。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=;
int n,k,L,R,d[maxn][],sum[maxn],p[maxn][],logs[maxn];
struct cyc{
int x,l,r,y;
bool operator < (const cyc &a) const
{return sum[y]-sum[x-]<sum[a.y]-sum[a.x-];}
}qp;
priority_queue<cyc>q;
void RMQ_init()
{
logs[]=-;for(int i=;i<=n;i++)logs[i]=logs[i>>]+;
for(int i=;i<=n;i++){d[i][]=sum[i];p[i][]=i;}
for(int j=;(<<j)<=n;j++)
for(int i=;i+(<<j)-<=n;i++)
{
d[i][j]=max(d[i][j-],d[i+(<<(j-))][j-]);
p[i][j]=d[i][j-]>d[i+(<<(j-))][j-]?p[i][j-]:p[i+(<<(j-))][j-];
}
}
int RMQ(int l,int r)
{
int K=logs[r-l+];
return d[l][K]>d[r-(<<K)+][K]?p[l][K]:p[r-(<<K)+][K];
}
int main()
{
scanf("%d%d%d%d",&n,&k,&L,&R);
sum[]=;
for(int i=;i<=n;i++){scanf("%d",&sum[i]);sum[i]+=sum[i-];}
RMQ_init();
for(int i=;i<=n;i++){
if(i+L-<=n)q.push((cyc){i,i+L-,min(n,i+R-),RMQ(i+L-,min(n,i+R-))});
}
long long ans=;
for(int i=;i<=k;i++)
{
qp=q.top();q.pop();
ans+=sum[qp.y]-sum[qp.x-];
if(qp.y>qp.l)q.push((cyc){qp.x,qp.l,qp.y-,RMQ(qp.l,qp.y-)});
if(qp.y<qp.r)q.push((cyc){qp.x,qp.y+,qp.r,RMQ(qp.y+,qp.r)});
}
printf("%lld",ans);
return ;
}