[文章目录]
Description
给你长为n的序列{a}，求长度在[L,R]的连续子段的和中前k大的和的和。n,k<=5*10^5 abs(ai)<=1000
据说这是一个套路，叫“超级钢琴”？
求前缀和。枚举左端点i，所有子段可以表示为s[i+l~i+r]-s[i]。那么这一类的最大值即为max{s[i+l~i+r]}-s[i]，假设为p，第二大值即为max{max(s[i+l~p-1]),max(s[p~i+r])}-s[i]。发现可以由最大找到次大来进行递推，并且权值是单调不增的。
ST算法预处理区间最值所在位置。维护一个大根堆，记录左端点以及右端点范围和权值，每次拿出堆顶，之后将下两个扔入堆中。时间复杂度O(nlogn+klogn)
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
x=0; char ch=nc(),f=0;
while(!isdigit(ch)) {if(ch=='-') f=1; ch=nc();}
while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
if(f) x=-x;
}
int n,k,L,R,a[501000];
struct node
{
int i,l,r,w;
};
bool operator < (const node x,const node y){return x.w<y.w;}
priority_queue<node>q;
int mx[501000][20],Log[501000];
inline int Min(int x,int y){return x<y ? x:y;}
inline int Max(int x,int y){return x>y ? x:y;}
int query(int l,int r)
{
int i=Log[r-l+1];
return Max(a[mx[l][i]],a[mx[r-(1<<i)+1][i]]);
}
ll ans;
int main()
{
scanf("%d%d%d%d",&n,&k,&L,&R);
for(int i=1;i<=n;++i) read(a[i]),a[i]+=a[i-1];
for(int i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
for(int i=1;i<=n;++i) mx[i][0]=i;
for(int i=1;i<=Log[R-L+1];++i)
for(int j=1;j+(1<<i)-1<=n;++j)
{
mx[j][i]=a[mx[j][i-1]] > a[mx[j+(1<<(i-1))][i-1]] ?
mx[j][i-1] : mx[j+(1<<(i-1))][i-1];
}
int tmp,lo,l,r;
for(int i=0;i+L<=n;++i)
{
l=i+L; r=Min(n,i+R);
q.push((node){i,l,r,query(l,r)-a[i]});
}
int x;
while(k--)
{
ans+=q.top().w; x=q.top().i; l=q.top().l; r=q.top().r; q.pop(); lo=Log[r-l+1];
tmp=a[mx[l][lo]] > a[mx[r-(1<<lo)+1][lo]] ? mx[l][lo] : mx[r-(1<<lo)+1][lo];
if(tmp!=l) q.push((node){x,l,tmp-1,query(l,tmp-1)-a[x]});
if(tmp!=r) q.push((node){x,tmp+1,r,query(tmp+1,r)-a[x]});
}
printf("%lld",ans);
return 0;
}