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

小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。

这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。

一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。

小Z决定创作一首由k个超级和弦组成的乐曲，为了使得乐曲更加动听，小Z要求该乐曲由k个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。

Solution

题目需要求一个数列的前k大的字段和。

因为字段的左右端点都是移动的，我们不能直接维护这么一个东西，更不能把所有合法子段都加入堆中贪心。

考虑固定一个端点。

对于一个固定的左端点，最优的右端点是确定的（可以用ST表O（1）找出来）。

所以我们把所有左端点都加入堆中，每次取出最大值后，将（l—pos-1）和（pos+1—r）加入堆（pos是上一次最优点）。

Code

#include<cstdio>

#include<queue>

#include<cmath>

#include<iostream>

#define N 500002

using namespace std;

typedef long long ll;

ll sum[N],st[N][],ans;

int pos[N][],n,k,l,r,ji[N];

ll RMQ(int l,int r){

    return max(st[l][ji[r-l+]],st[r-(<<ji[r-l+])+][ji[r-l+]]);

}

struct node{

    int tag,l,r;

    ll num;

    bool operator < (const node &b)const{

        return num<b.num;

    }

};

priority_queue<node>q;

int main(){

    scanf("%d%d%d%d",&n,&k,&l,&r);

    for(int i=;i<=n;++i){scanf("%lld",&sum[i]);sum[i]+=sum[i-];st[i][]=sum[i];pos[i][]=i;}

    for(int i=;i<=n;++i)ji[i]=log(i)/log();

    for(int i=;(<<i)<=n;++i)

      for(int j=;j<=n;++j){

          st[j][i]=st[j][i-];pos[j][i]=pos[j][i-];

          if(j+(<<i-)<=n&&st[j+(<<i-)][i-]>st[j][i]){

              st[j][i]=st[j+(<<i-)][i-];

              pos[j][i]=pos[j+(<<i-)][i-];;

          }

      }

    for(int i=;i<=n;++i)

    if(i+l-<=n)q.push(node{i,i+l-,min(i+r-,n),RMQ(i+l-,min(i+r-,n))-sum[i-]});

    while(k--){

        node x=q.top();q.pop();

        int pp=ji[x.r-x.l+];

        int po=pos[x.l][pp];

        if(sum[pos[x.r-(<<pp)+][pp]]>sum[po])po=pos[x.r-(<<pp)+][pp];

        ans+=x.num;

        int lp=po-;

        if(x.l<=lp)q.push(node{x.tag,x.l,lp,RMQ(x.l,lp)-sum[x.tag-]});

        lp=po+;

        if(lp<=x.r)q.push(node{x.tag,lp,x.r,RMQ(lp,x.r)-sum[x.tag-]});

    }

    printf("%lld",ans);

    return ;

}