题解 | #超级钢琴#

ST 表 + 优先队列 + 前缀和

题意

给一个长度 为 n 的序列，让你从中选 k 个长度在 [L,R] 范围内的区间 (同一个区间不可选多次)
要求：这 k 个区间的区间和 相加 得到的值 应该最大 

思路

(1):求出前缀和
(2):枚举 i 令其作为区间左边界，则右边界ri可取值 [i+L-1,i+R-1]
使用RMQ在区间[i+L-1,i+R-1]里找到pos => 目标区间里最大值的下标，即：对于左端点 i 有最大区间和 sum[pos] - sum[i-1]
同时，我们把 {i:此时的左边界,i+L-1:右边界最小值,i+R-1:右边界最大值,最大区间和} 作为一个结构体放到优先队列里面
重复执行上述过程，直到 i 枚举结束
(3) 弹出最大值
优先队列 每次会弹出一个 最大区间和 最大的结构体，该结构里含的最大区间和 对答案有贡献
假设此时弹出的结构体为{id,l,r,sum[pos]-sum[id-1]}
即：对于左端点id 其右端点取 pos 时，对答案有贡献
我们不立刻把它舍弃，因为对于左端点 id，其他合法的右端点对答案可能也会有贡献
所以我们在弹出它后，还要把{id,l,pos-1,maxm1}、{id,pos+1,r,maxm2} 给入队，来更新下一个最大值

综上：Code 如下

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5+10;

typedef long long ll;

int lg[N];
int sum[N];
int f[N][20];
int n,k,L,R;
struct node{
    int id;
    int l,r;
    int maxm;
    bool operator < (const node & x) const{
        return maxm < x.maxm;
    }
};

void ST(){
    lg[1]=0;
    lg[2]=1;
    for(int i=3;i<=n;i++) lg[i]=lg[i/2]+1;

    int len=lg[n];
    for(int j=1;j<=len;j++) for(int i=1;i-1+(1<<j)<=n;i++) {
        int x=f[i][j-1],y=f[i+(1<<(j-1))][j-1];
        f[i][j]=sum[x]>sum[y]?x:y;
    }
}

int query(int l,int r){
    int len=lg[r-l+1];
    int x=f[l][len],y=f[r+1-(1<<len)][len];
    return sum[x]>sum[y]?x:y;
}

int main(){
    cin>>n>>k>>L>>R;
    for(int i=1;i<=n;i++) cin>>sum[i],sum[i]+=sum[i-1],f[i][0]=i;
    ST();

    priority_queue<node>q;
    for(int i=1;i<=n;i++) {
        if(i+L-1>n) break;
        if(i+L-1==n) q.push({i,n,n,sum[n]-sum[i-1]});
        else if(n>i+L-1) {
            int x=query(i+L-1,min(n,i+R-1));
            q.push({i,i+L-1,min(n,i+R-1),sum[x]-sum[i-1]});
        }  
    }

    ll ans=0; 
    while(k--){
        auto t=q.top();
        q.pop();
        int id=t.id,l=t.l,r=t.r,maxm=t.maxm;
        ans+=maxm;

        int index=query(l,r);
        if(index-1>=l){
            int x=query(l,index-1);
            q.push({id,l,index-1,sum[x]-sum[id-1]});
        } 
        if(index+1<=r){
            int x=query(index+1,r);
            q.push({id,index+1,r,sum[x]-sum[id-1]});
        } 
    }
    cout<<ans<<endl;

    return 0;
}