题解 P2048 【[NOI2010]超级钢琴】

2019-10-01 18:55:32


我要解出一个

i l r x v的 组

我可以查找的是一个最大值

并且我要知道他在哪个位置

查最大值ST表即可

但是查找位置的话

st表是不是也可以直接维护处位置来

答案是肯定的

只要开一个数组记录(一个2的j次方的最大值)

在哪一个位置即可

贪心每次取出最大的并将最大的分裂成为

i l x-1 posl vl

i x+1 r pos2 vr

即可

最后不要忘记要开long long

#include<bits/stdc++.h>

using namespace std;

#define int long long

inline int read(){
    int x=0,f=1;
    char p=getchar();
    while(!isdigit(p)){
        if(p=='-') f=-1;
        p=getchar();
    }
    while(isdigit(p)) x=(x<<3)+(x<<1)+p-48,p=getchar();
    return x*f;
}

const int maxn=5e5+5;

struct node{
    int start,l,r,val,pos;
    bool operator <(const node x)const{
        return x.val>val;
    }
};

int f[maxn][21],p[maxn][21],n,m,L,R,ans,x[maxn],sum[maxn];

priority_queue<node> q;

inline void pre_work(){
    for(int j=1;j<=19;j++)
        for(int i=1;i+(1<<j)-1<=n;i++){
            if(f[i][j-1]<f[i+(1<<j-1)][j-1]){
                f[i][j]=f[i+(1<<j-1)][j-1];
                p[i][j]=p[i+(1<<j-1)][j-1];
            }
            else{
                f[i][j]=f[i][j-1];
                p[i][j]=p[i][j-1];
            }
        }
}

inline pair<int,int> query(int l,int r){
    int t=log2(r-l+1);
    pair<int,int> pi;
    if(f[l][t]<f[r-(1<<t)+1][t]){
        pi.first=f[r-(1<<t)+1][t];
        pi.second=p[r-(1<<t)+1][t];
    } 
    else{
        pi.first=f[l][t];
        pi.second=p[l][t];
    }
    return pi;
}

signed main(){
    n=read();m=read();L=read();R=read();
    for(int i=1;i<=n;i++) x[i]=read(),p[i][0]=i;
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+x[i];
    for(int i=1;i<=n;i++) f[i][0]=sum[i];
    pre_work();
    for(int i=1;i<=n;i++){
        if(i+L-1<=n){
            int l=i+L-1,r=min(i+R-1,n);
            pair<int,int> pi=query(l,r);
            q.push((node){i,l,r,pi.first-sum[i-1],pi.second});
        }
        else break;
    }
//  cout<<"%^&"<<endl;
    while(m--){
    //  cout<<ans<<endl;
        node a=q.top();
        q.pop();
        ans+=a.val;
        if(a.pos==a.l){
    //      cout<<"$%^"<<endl;
            if(a.l==a.r) continue;
            pair<int,int> pi=query(a.l+1,a.r);
    //      cout<<":"<<endl;
            q.push((node){a.start,a.l+1,a.r,pi.first-sum[a.start-1],pi.second});
        }
        else if(a.pos==a.r){
            if(a.l==a.r) continue;
            pair<int,int> pi=query(a.l,a.r-1);
            q.push((node){a.start,a.l,a.r-1,pi.first-sum[a.start-1],pi.second});
        }
        else{
            pair<int,int> pi=query(a.l,a.pos-1);
            q.push((node){a.start,a.l,a.pos-1,pi.first-sum[a.start-1],pi.second});
            pi=query(a.pos+1,a.r);
            q.push((node){a.start,a.pos+1,a.r,pi.first-sum[a.start-1],pi.second});  
        }
    }
    cout<<ans<<endl;
    return 0;
}