P2048 [NOI2010]超级钢琴

传送门

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

题意：

给你 $\\{ 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);
}