BZOJ 2006:[NOI 2010]スーパーピアノ【欲張り】

Description
Zさんは有名なピアニストで、最近C博士はZさんにスーパーピアノをあげました.Zさんはこのピアノで世界で一番すばらしいものを作りたいと思っています.
音楽.このスーパーピアノはn個の音符を弾くことができ、番号は1からnです.i番目の音符の美しさはAiで、その中でAiはプラスとマイナスです.スーパー
和弦」は、複数の番号の連続する音符からなり、含まれる音符の個数はL以上R以下である.スーパーハーモニーの美しさを定義します
すべての音符の美しさの和.2つのスーパーハーモニーは同じと考えられ、この2つのスーパーハーモニーに含まれる音符の集合が同じである場合のみである.
小Zはk個のスーパーハーモニーからなる楽曲を創作することを決定し、楽曲をより美しくするために、小Zはこの楽曲にk個の異なるスーパーハーモニーからなることを要求した.
私たちは1曲の楽曲の美しさをその含むすべてのスーパー和弦の美しさの和として定義します.Zさんは彼が作ることができる楽曲のすばらしさを知りたいです.
大きい値はいくらですか.
問題解
この問題は「スーパーピアノ」という欲張りだ.
すべての和弦のすばらしさを扱うことができれば,直接前kの大きさを取ればよいが,これは不可能であるため,各位置を左端点とする最適解を先に処理し,これらの解の最大値は必ず最大の和弦であり,その後,この最適解の位置を削除し,残りの位置の最適解を得る.最適解の位置をtとし,iを最短点とする区間の右端点範囲を[L,R]とすると,tという点は区間を[L,t−1]と[t+1,R]に分割し,これにより,スタックを維持し,最適解を取得するたびに新しいノードを挿入するたびにlogの複雑さとなり,前処理用STテーブルでよい.
コード#コード#

#include
#include
#include
#include
#include
#define maxn 500006
#define LL long long
using namespace std;
inline char nc(){
    static char buf[100000],*i=buf,*j=buf;
    return i==j&&(j=(i=buf)+fread(buf,1,100000,stdin),i==j)?EOF:*i++;
}
inline int _read(){
    char ch=nc();int sum=0,p=1;
    while(ch!='-'&&!(ch>='0'&&ch<='9'))ch=nc();
    if(ch=='-')p=-1,ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum*p;
}
int n,T,L,R,sum[maxn],f[maxn][20],g[maxn][20];
LL ans;
struct data{
    int s,l,r,t,sum;
    bool operator return sumsum;}
};
priority_queue  heap;
void ST(){
    for(int j=1;j<=log2(n);j++)
     for(int i=0;i<=n-(1<1;i++)
      if(f[i][j-1]>f[i+(1<1))][j-1])f[i][j]=f[i][j-1],g[i][j]=g[i][j-1];
                                   else f[i][j]=f[i+(1<1))][j-1],g[i][j]=g[i+(1<1))][j-1];
}
inline int get(int l,int r){
    int j=log2(r-l+1);
    return (f[l][j]>f[r-(1<1][j])?g[l][j]:g[r-(1<1][j];
}
int main(){
    freopen("piano.in","r",stdin);
    freopen("piano.out","w",stdout);
    n=_read();T=_read();L=_read();R=_read();
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+_read(),f[i][0]=sum[i],g[i][0]=i;
    ST();
    for(int i=0;i<=n-L;i++){
        data p;
        p.s=i;p.l=i+L;p.r=min(n,i+R);
        p.t=get(p.l,p.r);p.sum=sum[p.t]-sum[i];
        heap.push(p);
    }
    while(T--){
        data p=heap.top(),p1,p2;heap.pop();
        ans+=p.sum;
        p1.s=p2.s=p.s;
        p1.l=p.l;p1.r=p.t-1;p2.l=p.t+1;p2.r=p.r;
        if(p1.l<=p1.r)p1.t=get(p1.l,p1.r),p1.sum=sum[p1.t]-sum[p1.s],heap.push(p1);
        if(p2.l<=p2.r)p2.t=get(p2.l,p2.r),p2.sum=sum[p2.t]-sum[p2.s],heap.push(p2);
    }
    printf("%lld",ans);
    return 0;
}