P2048 [NOI2010]超级钢琴（RMQ+堆+贪心）

P2048 [NOI2010]超级钢琴

区间和--->前缀和做差

多次查询区间和最大--->前缀和RMQ

每次取出最大的区间和--->堆

于是我们设个3元组$(o,l,r)$，表示左端点为$o$，右端点在$l,r$之间（最优处为$t$）的最大区间和。

$t$可以RMQ在$l,r$间$O(1)$查询

所以我们事先把$n$个三元组(1<=o<=n)扔到堆里，每次把$s[t]-s[o-1]$最大的拿出来累加进答案。

取出来后$[o,t]$就不能取了，于是我们再把$(o,l,t-1)$和$(o,t+1,r)$再扔进堆里就好辣

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define rint register int

using namespace std;

inline int Min(int a,int b){return a<b?a:b;}

void read(int &x){

    char c=getchar();x=; bool f=;

    while(c<''||c>'') f=f&&(c!='-'),c=getchar();

    while(''<=c&&c<='') x=x*+(c^),c=getchar();

    x=f?x:-x;

}

#define N 500005

int n,k,s[N],f[][N],Log[N],a,L,R; long long ans;

void maketb(){//RMQ：f数组存的是最大值的下标

    for(rint i=;i<=n;++i) f[][i]=i;

    for(rint j=;(<<j)<=n;++j)

        for(rint i=;i+(<<(j-))<=n;++i){

            if(s[f[j-][i]]>s[f[j-][i+(<<(j-))]])

                f[j][i]=f[j-][i];

            else f[j][i]=f[j-][i+(<<(j-))];

        }

}

int ask(int l,int r){

    int k=Log[r-l+];

    if(s[f[k][l]]>s[f[k][r-(<<k)+]]) return f[k][l];

    else return f[k][r-(<<k)+];

}

struct data{

    int o,l,r,t;

    data(int A,int B,int C):

        o(A),l(B),r(C),t(ask(B,C))

    {}

    bool operator < (const data &tmp) const{

        return s[t]-s[o-]<s[tmp.t]-s[tmp.o-];

    }

};priority_queue <data> h;

int main(){

    read(n);read(k);read(L);read(R); Log[]=-;

    for(rint i=;i<=n;++i) read(a),s[i]=s[i-]+a,Log[i]=Log[i>>]+;

    maketb();

    for(rint i=;i+L-<=n;++i) h.push(data(i,i+L-,Min(i+R-,n)));

    while(k--){

        data x=h.top(); h.pop();

        ans+=s[x.t]-s[x.o-];

        if(x.l<x.t) h.push(data(x.o,x.l,x.t-));

        if(x.r>x.t) h.push(data(x.o,x.t+,x.r));

    }printf("%lld",ans);

    return ;

}

P2048 [NOI2010]超级钢琴（RMQ+堆+贪心）的相关教程结束。