Luogu

BZOJ

分析

堆+主席树。

考虑对于每个左端点 $l$ ，先找到一个 $r$ 使得 $\sum\limits_{i=l}^ra[i]$ 最大。

设 $s[i]=\sum\limits_{j=1}^i a[i]$ ，也就是说要找到一个 $r$ 使得 $sum[r]-sum[l-1]$ 最大。

显然只要在 $r$ 的范围内找区间最大值就行了，因为 $sum[l-1]$ 是定值。

这样子就找到了一些和弦，把这些和弦丢到一个以美妙度为关键字的大根堆里去。

那么我们取出堆顶，这样就有了一个最大值。那么下一个可能成为最大值的有所有堆中的元素，以及这个最大值对应的左端点对应的区间的第 $2$ 大值。

于是重复这个过程，每次取出堆顶（假设是第 $k$ 大值），然后把对应的第 $k+1$ 大值丢进去。当已经是最小值的时候就不用丢了。

把这个过程进行 $k$ 遍就求出了答案。

至于怎么查第 $k$ 大，拿个主席树维护一下就行了。

细节比较多。具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;

int a[N],s[N],S[N],rt[N];
struct node { int p,cnt,val; };
bool operator <(node a,node b) { return a.val<b.val; }
priority_queue<node> Q;

struct President_Tree {
    struct node { int ls,rs,sum; } t[N*30];
    int tot;
    
    President_Tree() { tot=0; }
    
    inline void modify(int& p,int q,int l,int r,int pos,int w) {
        t[p=++tot]=t[q];
        if (l==r) { t[p].sum+=w; return; }
        int mid=(l+r)>>1;
        if (pos<=mid) modify(t[p].ls,t[q].ls,l,mid,pos,w);
        else modify(t[p].rs,t[q].rs,mid+1,r,pos,w);
        t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum;
    }
    inline int query(int p,int q,int l,int r,int k) {
        if (l==r) return l;
        int mid=(l+r)>>1,rsum=t[t[q].rs].sum-t[t[p].rs].sum;
        if (rsum>=k) return query(t[p].rs,t[q].rs,mid+1,r,k);
        else return query(t[p].ls,t[q].ls,l,mid,k-rsum);
    }
} T;


int main() {
    int n=read(),K=read(),L=read(),R=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) s[i]=s[i-1]+a[i];
    for (re int i=1;i<=n;++i) S[i]=s[i];
    sort(S+1,S+n+1); int top=unique(S+1,S+n+1)-S-1;
    for (re int i=1;i<=n;++i) s[i]=lower_bound(S+1,S+top+1,s[i])-S;
    for (re int i=1;i<=n;++i) T.modify(rt[i],rt[i-1],1,top,s[i],1);
    for (re int i=1;i+L-1<=n;++i) {
        int j=i+L-1,k=min(i+R-1,n);
        int v=S[T.query(rt[j-1],rt[k],1,top,1)]-S[s[i-1]];
        Q.push((node){i,1,v});
    }
    ll ans=0;
    while (K--) {
        node tp=Q.top(); Q.pop();
        ans+=tp.val; ++tp.cnt;
        int lim=min(n,tp.p+R-1)-(tp.p+L-1)+1;
        if (tp.cnt>lim) continue;
        int i=tp.p+L-1,j=min(tp.p+R-1,n);
        int v=S[T.query(rt[i-1],rt[j],1,top,tp.cnt)]-S[s[tp.p-1]];
        Q.push((node){tp.p,tp.cnt,v});
    }
    printf("%lld\n",ans);
    return 0;
}