Steven_Meng's Blog

传送门

强烈谴责出题者，题面都花了好几分钟读。

题意：

给你$\\{ A_i\\}$，让你从集合$S=\\{x|x= \sum _{k=i} ^{j} A[k] , j-i+1 \in[L,R] \\}$选出$k$个数，使他们的和尽可能大。

首先考虑一件事，如何表示$[i,j]$。

一种思路是枚举区间长度$l$，$l \in [L,R],[1,l],[2,l+1],[3,l+2] \cdots$，但是这样不好表示。

另一种思路是枚举左端点$i$，$i \in [1,n-L+1] , [i,i+L-1],[i,i+L], \cdots [i,i+R-1]$，这样就有了确定的范围。

我们有一个显然的贪心，要从$S$中选出前$k$大的值。

设$Max(i,j,k)=使\sum _{p=i} ^a A[p]最大的 a，且a \in [j,k]$

考虑$S$中最大值，肯定是$\sum _{j=i} ^{Max(i,i+L-1,i+R-1)} A[j]$中的一个，根据贪心，我们要取走这个最大值，设这个最大值的$i$为$p_1$，设$Max(p_1,p_1+L-1,p_1+R-1)=p_2$那么取走它之后，显然它会分裂成两个，之后的最大值只可能在$Max(p_1,p_1+L-1, p_2-1),Max(p_1,p_2+1,p_1+R-1)$中取到。

于是由上述性质，我们需要用堆维护，每次将某个数取走之后，将分裂成的两个数$push$进去即可。

这个$Max(i,j,k)$也比较好求，$\sum _{p=i} ^a A[p] \Rightarrow sum[a]-sum[i-1]$，用$ST$表维护使$sum[i]$最大的位置即可。

#include <bits/stdc++.h>
#define MAXN 500005
#define LOG 25
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN],sum[MAXN],n,k,L,R;
namespace RMQ{
    int pos[LOG][MAXN],lg[MAXN];
    inline int cmp(int x,int y){
        return sum[x]<sum[y];
    }
    inline void Init(){
        lg[0]=-1;
        for (register int i=1;i<MAXN;++i){
            lg[i]=lg[i>>1]+1;
        }
        for (register int i=1;i<=n;++i) pos[0][i]=i;//注意是位置
        for (register int i=1;i<LOG;++i){
            for (register int j=1;j+(1<<i)-1<=n;++j){
                pos[i][j]=max(pos[i-1][j],pos[i-1][j+(1<<(i-1))],cmp);
            }
        }
    }
    inline int Query(int l,int r){
        int k=lg[r-l+1];
        return max(pos[k][l],pos[k][r-(1<<k)+1],cmp);
    }
}
using namespace RMQ;
struct Piano{
    int p,l,r,m;
};
inline Piano make(int p,int l,int r){
    return Piano{p,l,r,Query(l,r)};
}
inline int Calc(const Piano &A){
    return sum[A.m]-sum[A.p-1];
}
inline bool operator < (const Piano &A,const Piano &B){
    return Calc(A)<Calc(B);
}
int main(){
    n=read(),k=read(),L=read(),R=read();
    for (register int i=1;i<=n;++i) a[i]=read();
    for (register int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
    Init();
    priority_queue<Piano>Q;
    for (register int i=1;i<=n-L+1;++i){
        Q.push(make(i,i+L-1,min(i+R-1,n)));
    }
    long long ans=0;
    while (k--){
        int p=Q.top().p,l=Q.top().l,r=Q.top().r,m=Q.top().m;
        ans+=Calc(Q.top());
        Q.pop();
        if (l<m) Q.push(make(p,l,m-1));
        if (m<r) Q.push(make(p,m+1,r));
        //分裂成两个区间
    }
    printf("%lld\n",ans);
}