首页 > 其他 > 详细

P2048 [NOI2010]超级钢琴(RMQ)

时间:2019-04-09 12:13:55      阅读:126      评论:0      收藏:0      [点我收藏+]

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=0; bool f=1;
    while(c<0||c>9) f=f&&(c!=-),c=getchar();
    while(0<=c&&c<=9) x=x*10+(c^48),c=getchar();
    x=f?x:-x;
}
#define N 500005
int n,k,s[N],f[19][N],Log[N],a,L,R; long long ans;
void maketb(){//RMQ:f数组存的是最大值的下标
    for(rint i=1;i<=n;++i) f[0][i]=i;
    for(rint j=1;(1<<j)<=n;++j)
        for(rint i=1;i+(1<<(j-1))<=n;++i){
            if(s[f[j-1][i]]>s[f[j-1][i+(1<<(j-1))]])
                f[j][i]=f[j-1][i];
            else f[j][i]=f[j-1][i+(1<<(j-1))];
        }
}
int ask(int l,int r){
    int k=Log[r-l+1];
    if(s[f[k][l]]>s[f[k][r-(1<<k)+1]]) return f[k][l];
    else return f[k][r-(1<<k)+1];
}
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-1]<s[tmp.t]-s[tmp.o-1];
    }
};priority_queue <data> h;
int main(){
    read(n);read(k);read(L);read(R); Log[0]=-1;
    for(rint i=1;i<=n;++i) read(a),s[i]=s[i-1]+a,Log[i]=Log[i>>1]+1;
    maketb();
    for(rint i=1;i+L-1<=n;++i) h.push(data(i,i+L-1,Min(i+R-1,n)));
    while(k--){
        data x=h.top(); h.pop();
        ans+=s[x.t]-s[x.o-1];
        if(x.l<x.t) h.push(data(x.o,x.l,x.t-1));
        if(x.r>x.t) h.push(data(x.o,x.t+1,x.r));
    }printf("%lld",ans);
    return 0;
}

 

P2048 [NOI2010]超级钢琴(RMQ)

原文:https://www.cnblogs.com/kafuuchino/p/10675992.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!