题意简述：
1.给你一个序列 $n$，求出每一个长度为 l~r 的子序列数值的和。
2.取出前 $k$ 大个，累及总和。
------------
Solution：
容易想到，求静态子序列之和，可以使用前缀和，区间 l~r 和即为 $pre[r]-pre[l-1]$。
于是可以暴力求出每个的和然后排序累加，但这样复杂度过高，会 TLE。
再想想，对于每一个超级和弦的起始点 k，终点的范围在 k+l-1~k+r-1 之间。
那么我们若能找出每一个 k 中，对应的终点中的最大值，不断取出最大值不就可以了吗？
显然是不可行的。
理由1：k 可能大于 $n$，即取完不够。
理由2：如图：
当 1~3,2~3 取完时，1~2 显然相对于其他解更优。
所以，当我们累加一个节点 mid 时，应考虑 l~mid-1，mid+1~r，将其加入候选队列，以避免漏掉更优解。
由此可见，我们需要维护 1.前缀和 2.RMQ 3.当前最优解（优先队列）。
同时，优先队列中维护五个元素：当前选取节点编号，当前的范围 l~r，当前的最大值，当前的超级和弦的来源。
注意：st 表维护的是前缀和最大值，优先队列则是区间和最大值。
我的写法貌似和其他人不大一样（跑得慢）代码内有注释：
#include<bits/stdc++.h>
using namespace std;
struct hx
{
long long now,lk,rk,val,pos;//当前选取编号，l~r，max，和弦来源
hx();
hx(long long _now,long long _lk,long long _rk,long long _val,long long _pos):now(_now),lk(_lk),rk(_rk),val(_val),pos(_pos){};
bool operator < (hx x) const
{
return val<x.val;
}
};//和弦结构体，并重载<，按值排序
priority_queue<hx> q;
long long n,k,l,r,st[23][2000500][2],hxt[2000500],ans;//st表，第三维0是维护区间前缀和最大值，1是区间前缀和最大值编号
//一开始没开long long错了，一气之下想都没想全开成long long
void st_pre()
{
for(int i=1;i<=20;i++)
{
for(int j=1;j<=n;j++)
{
if(st[i-1][j][0]<st[i-1][j+(1<<(i-1))][0]) st[i][j][0]=st[i-1][j+(1<<(i-1))][0],st[i][j][1]=st[i-1][j+(1<<(i-1))][1];
else st[i][j][0]=st[i-1][j][0],st[i][j][1]=st[i-1][j][1];
}//在更新区间前缀和最大值时同时更新最大值位置（稍微改下模板）
}
}//st表预处理
int main()
{
scanf("%lld %lld %lld %lld",&n,&k,&l,&r);//读入
for(int i=1;i<=n;i++) scanf("%lld",&st[0][i][0]),st[0][i][0]+=st[0][i-1][0],st[0][i][1]=i;//维护初始前缀和最大值与初始位置
st_pre();
for(int i=1;i<=20;i++) hxt[1<<i]++;
for(int i=1;i<=n;i++) hxt[i]+=hxt[i-1];//O(1)询问预处理
for(int i=1;i<=n-l+1;i++)
{
long long ll=i+l-1,rr=min(n,i+r-1),len=rr-ll+1;//左，右，长度，注意范围取min
long long max1=st[hxt[len]][ll][0],max2=st[hxt[len]][rr-(1<<hxt[len])+1][0],id1=st[hxt[len]][ll][1],id2=st[hxt[len]][rr-(1<<hxt[len])+1][1];//这四个变量其实就是st表中两段区间内的前缀和最大值与编号，取max
if(max1<max2) q.push(hx(id2,ll,rr,max2-st[0][i-1][0],i));
else q.push(hx(id1,ll,rr,max1-st[0][i-1][0],i));//插入大的，同时用前缀和最大值减去起始点-1，得到序列和
}
int js=0;
while(js<k)
{
js++;
ans=ans+q.top().val;//更新
long long ll=q.top().lk,rr=q.top().rk,mid=q.top().now,poss=q.top().pos;//左端点，右端点，上次取的位置，原本起点
if(mid>ll)//左边有可更新插入的
{
mid--;//因为不能重复取mid，故减一
long long len=mid-ll+1,max1=st[hxt[len]][ll][0],max2=st[hxt[len]][mid-(1<<hxt[len])+1][0],id1=st[hxt[len]][ll][1],id2=st[hxt[len]][mid-(1<<hxt[len])+1][1];
if(max1<max2) q.push(hx(id2,ll,mid,max2-st[0][poss-1][0],poss));
else q.push(hx(id1,ll,mid,max1-st[0][poss-1][0],poss));//插入堆
mid++;//一定要记得回来，下面可能还用到
}
if(rr>mid)//同上，右边情况
{
mid++;
long long len=rr-mid+1,max1=st[hxt[len]][mid][0],max2=st[hxt[len]][rr-(1<<hxt[len])+1][0],id1=st[hxt[len]][mid][1],id2=st[hxt[len]][rr-(1<<hxt[len])+1][1];
if(max1<max2) q.push(hx(id2,mid,rr,max2-st[0][poss-1][0],poss));
else q.push(hx(id1,mid,rr,max1-st[0][poss-1][0],poss));
mid--;
}
q.pop();
}
printf("%lld",ans);//输出结果
return 0;
}
题解清楚么？
return 0；
原文：https://www.cnblogs.com/wxg-Jay/p/12239549.html