【bzoj 2006】[NOI 2010]スーパーピアノスタック+st表

Description
Zさんは有名なピアニストで、最近C博士はZさんにスーパーピアノをあげました.Zさんはこのピアノで世界で一番すばらしい音楽を作りたいと思っています.このスーパーピアノはn個の音符を弾くことができ、番号は1からnです.i番目の音符の美しさはAiで、その中でAiはプラスとマイナスです.1つの「スーパーハーモニー」は、複数の番号の連続した音符からなり、含まれる音符の個数はL以上R以下である.スーパーハーモニーの美しさを、その含まれるすべての音符の美しさの和として定義します.2つのスーパーハーモニーは同じと考えられ、この2つのスーパーハーモニーに含まれる音符の集合が同じである場合のみである.小Zはk個のスーパーハーモニーからなる楽曲を創作することを決定し、楽曲をより美しくするために、小Zはこの楽曲にk個の異なるスーパーハーモニーからなることを要求した.私たちは1曲の楽曲の美しさをその含むすべてのスーパー和弦の美しさの和として定義します.Zちゃんは彼が作ることができる楽曲の美しさの最大値がどれくらいなのか知りたいです.
Input
第1行は4つの正の整数n,k,L,Rを含む.ここでnは音符の個数,kは楽曲に含まれるスーパー和弦の個数,LとRはそれぞれスーパー和弦に含まれる音符の個数の下限と上限である.次のn行は、各行に1つの整数Aiを含み、各音符の美しさを小さいから大きいまで番号で表す.
Output
楽曲の美しさの最大値を表す整数は1つしかありません.
Sample Input

4 3 2 3



3



2



-6



8

Sample Output

11

【サンプル説明】
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である.
HINT
Source
考えが素晴らしい...
定義(i,l,r,t)は、現在の左端点がiであり、右端点選択区間が[l,r]であり、現在の最適右端点がtである場合、現在区間の重み値はsum[t]−sum[i−1]である.
次に、現在の前k大区間を格納し、重み値でソートするスタックを維持します.毎回一番大きいのを取り出して、(i,l,t-1,t 1)と(i,t+1,r,t 2)に分裂して、それから続ければいいので、全部でk回取り出して、一つ取り出しても答えです.このように毎回取り出すのは一番大きいです.
tの算出方法については,区間[l,r]の中からsum[t]−sum[i−1]が最大となるtを選択した.sum[i−1]は固定であることを見出したので,sum[t]を最大にすればよい,これはRMQ問題であり,stテーブルはO(1)でよい.
1つずつ取り出して2つ入れるので、最後のスタックにはn+k個の要素があり、複雑度はO(klog(n+k))です.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cmath>
using namespace std;

typedef long long LL;
const int SZ = 1000010; 

int n,k,L,R;
LL num[SZ];

struct qj{
    int i,l,r,t;
};

bool operator <(qj a,qj b)
{
    return num[a.t] - num[a.i - 1] < num[b.t] - num[b.i - 1];
}

priority_queue<qj> q;


int mx[SZ][30]; 

void get_st()
{
    for(int i = 1;i <= n;i ++) mx[i][0] = i;
    for(int j = 1;j <= log2(n);j ++)
        for(int i = 1;i <= n;i ++)
        {
            int x = mx[i][j - 1];
            int y = mx[i + (1 << (j - 1))][j - 1];
            mx[i][j] = num[x] < num[y] ? y : x;
        }
}

int ask(int l,int r)
{
    int k = log2(r - l + 1);
    int x = mx[l][k],y = mx[r - (1 << k) + 1][k];
    return num[x] < num[y] ? y : x;
}

int main()
{
    scanf("%d%d%d%d",&n,&k,&L,&R);
    for(int i = 1;i <= n;i ++)
        scanf("%lld",&num[i]);
    for(int i = 1;i <= n;i ++)
        num[i] += num[i - 1];
    get_st();
    for(int i = 1;i <= n;i ++)
    {
        if(i + L - 1 <= n)
        {
            int l = i + L - 1;
            int r = min(i + R - 1,n);
            q.push((qj){i,l,r,ask(l,r)});
        }
    } 
    LL ans = 0;
    while(k --)
    {
        qj x = q.top(); q.pop();
        ans += num[x.t] - num[x.i - 1];
        if(x.t != x.l) q.push((qj){x.i,x.l,x.t - 1,ask(x.l,x.t - 1)});
        if(x.t != x.r) q.push((qj){x.i,x.t + 1,x.r,ask(x.t + 1,x.r)});
    }
    printf("%lld
",ans);
    return 0; 
}
/* 1 1 1 1 */