题解【NOI2010】超级钢琴

【NOI2010】超级钢琴

Description

小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。
这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。
一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。
小Z决定创作一首由k个超级和弦组成的乐曲，为了使得乐曲更加动听，小Z要求该乐曲由k个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。

Input

第一行包含四个正整数n, k, L, R。其中n为音符的个数，k为乐曲所包含的超级和弦个数，L和R分别是超级和弦所包含音符个数的下限和上限。
接下来n行，每行包含一个整数Ai，表示按编号从小到大每个音符的美妙度。

Output

只有一个整数，表示乐曲美妙度的最大值。

Sample Input

Sample Output

11

Hint

【样例说明】
共有5种不同的超级和弦：
音符1 ~ 2，美妙度为3 + 2 = 5
音符2 ~ 3，美妙度为2 + (-6) = -4
音符3 ~ 4，美妙度为(-6) + 8 = 2
音符1 ~ 3，美妙度为3 + 2 + (-6) = -1
音符2 ~ 4，美妙度为2 + (-6) + 8 = 4
最优方案为：乐曲由和弦1，和弦3，和弦5组成，美妙度为5 + 2 + 4 = 11。
数据规模：

所有数据满足：-1000 ≤ Ai ≤ 1000，1 ≤ L ≤ R ≤ n且保证一定存在满足要求的乐曲。

Source

NOI， RMQ，堆，线段树

这应该是道NOI的水题了吧（连我都能做）。。

首先，这题用线段树似乎会被卡掉。。

但这题不需要修改！

因此，我们可以用O(logn)预处理，O(1)询问的ST表。

至于ST表，请移步百度。。。

对于每个节点x，首先求出在区间(x-R,x-L)中与x组成超级和弦的美妙度最大的点p。

然后将x,p,l,r，以及美妙度sum放入一个结构体。

以sum的值维护一个大根堆（可以用优先队列）

接下来，每取出一个美妙度，就再求出在区间（l,p-1）和区间(p+1,r)中与x组成超级和弦的美妙度最大的点p2。

再把他们放入结构体，再放进优先队列就行了！

具体方式请看代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

inline int gi(){
    ll sum=0,f=1;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return f*sum;
}

struct node{
    ll sum,now;
    int x,l,r;
    friend bool operator < (node a,node b){
        return a.sum<b.sum;
    }
};
int n,k,l,r,len;
int a[500001],s[500001]/*前缀和*/;
int f[500001][23]/*从i开始长度为power(2,j)(包括i)的区间的前缀和最小值*/;
int p[500001][23]/*从i开始长度为power(2,j)(包括i)的区间的前缀和最小值的位置*/;
int t[30]/*2的i次方*/,v[500001]/*满足power(2,p)<=i的最大的p*/;
ll ans=0;
priority_queue <node> que;

int power(int a,int b){
    int r=1;
    while(b){
        if((b&1)) r*=a;
        a*=a;
        b>>=1;
    }
    return r;
}

void pre(){
    v[0]=-1;
    for(int i=1;i<=n;i++){
        v[i]=v[i>>1]+1;
    }
    for(int j=0;j<=23;j++){
        t[j]=power(2,j);
    }
    for(int i=1;i<=n;i++){
        f[i][0]=s[i];
        p[i][0]=i;
    }
    for(int j=1;j<=23;j++){        
        for(int i=0;i<=n;i++){
            int o=j-1;
            if(i+t[j]>n+1) break;
            if(f[i][o]<f[i+t[o]][o]){
                p[i][j]=p[i][o];
                f[i][j]=f[i][o];
            }
            else{
                p[i][j]=p[i+t[o]][o];
                f[i][j]=f[i+t[o]][o];  
            }
        }
    }
}

void add(int i,int l,int r){
    if(r<0||r<l) return ;
    if(l<0) l=0;
    int kk;
    int q=v[r-l+1];
    if(f[l][q]<f[r-t[q]+1][q]){
        kk=p[l][q];
    }
    else kk=p[r-t[q]+1][q];
    node a;
    a.x=kk;a.sum=s[i]-s[kk];
    a.l=l;a.r=r;
    a.now=i;
    que.push(a);
}

void work(){
    for(int i=1;i<=n;i++){
        add(i,i-r,i-l);
    }
    for(int i=1;i<=k;i++){
        node a=que.top();
        que.pop();
        ans+=a.sum;
        add(a.now,a.l,a.x-1);
        add(a.now,a.x+1,a.r);
    }
}

int main()
{
    n=gi();k=gi();l=gi();r=gi();
    len=r-l+1;
    for(int i=1;i<=n;i++){
        a[i]=gi();
        s[i]=s[i-1]+a[i];
    }
    pre();
    work();
    printf("%lld
",ans);
    return 0;
}