[NOI2010]超级钢琴

Link
我们先来考虑朴素算法：将所有的方案求出来，然后排序。但是这样当然是不可能过的。
对于某一个区间的综合我们肯定很自然地想到前缀和。
那首先定住一个左节点$X$，那么这个区间的右端点肯定处于$[X + L - 1, X + R - 1]$之间。
那么如果我们想要求这个区间里面的最大值，可以考虑使用询问时间复杂度为$O(1)$的$ST$表。
如果右端点为$Y$，那么区间的值就是$Sum[Y] - Sum[X]$，那么我们可以直接寻找右端点区间中的$Sum[i]$的最大值。
然后我们就得到了一堆区间的最大值，一共应该是$N - R + 1$，但是$K$是有可能大于这个数的，因此我们不能只求这个区间的最大值。
于是考虑将这个区间二分。
具体来说，就是首先将所有以$i$左端点，右端点在$[X + L - 1, X + R - 1]$的一个结构体存储到一个大根堆中，当然，本人使用的是单调队列，因为这样结构比较清晰。
然后循环$K$次，每次取出堆顶计入答案。
接下来的操作是以当前答案所处的右端点为中间，二分$[X + L - 1, X + R - 1]$这个区间，分别加入单调队列。因为如果想要寻找原来右端点区间中的第二大，第三大，我们选择去掉当前的最大值，然后将它的左边和右边分别入队，算法正确性就可以保证了。

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

typedef long long LL ;
const int MAXN = 500010 ;
const int MAXM = 500010 ;
const int Inf = 0x7fffffff ;

LL N, K, L, R, Muc[MAXN] ;
long long  Sum[MAXN], Max[MAXN][20] ;
long long Ans ;

inline long long Read() {
    long long X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
    return X * F ;
}

inline void ST_BUILD() {
    for (int i = 1 ; i <= N ; i ++) Max[i][0] = i ;
    for (int j = 1 ; (1 << j) <= N ; j ++)
    for (int i = 1 ; i + (1 << j) - 1 <= N ; i ++) {
        int X = Max[i][j - 1] ;
        int Y = Max[i + (1 << (j - 1))][j - 1] ;
        if (Sum[X] > Sum[Y]) Max[i][j] = X ;
        else Max[i][j] = Y ;
    }
}

inline int Query(int L, int R) {
    int T = log2(R - L + 1) ;
    int X = Max[L][T], Y = Max[R - (1 << T) + 1][T] ;
    return Sum[X] > Sum[Y] ? X : Y ;
}

struct Q {
    int X, L, R, P ;
    Q() {} Q (int X, int L, int R) : X(X), L(L), R(R), P(Query(L, R)) {}
        friend bool operator < (const Q & A, const Q & B) {
            return Sum[A.P] - Sum[A.X - 1] < Sum[B.P] - Sum[B.X - 1] ;
    }
} ;

priority_queue<Q> E ;

int main() {
    N = Read(), K = Read(), L = Read(), R = Read() ;
    for (int i = 1 ; i <= N ; i ++) {
        Muc[i] = Read() ;
        Sum[i] = Sum[i - 1] + Muc[i] ;
    }   ST_BUILD() ;
    for (int i = 1 ; i <= N ; i ++)
        if (i + L - 1 <= N) 
            E.push(Q(i, i + L - 1, min(i + R - 1, N))) ;
    for (int i = 1 ; i <= K ; i ++) {
        int X = E.top().X, l = E.top().L, r = E.top().R, P = E.top().P ;
        E.pop() ; Ans += Sum[P] - Sum[X - 1] ;
        if (l != P) E.push(Q(X, l, P - 1)) ;
        if (r != P) E.push(Q(X, P + 1, r)) ;

    }   printf("%lld\n", Ans) ; return 0 ;
}