P2048 [NOI2010]超级钢琴 rmq+优先队列

题目链接：https://www.luogu.com.cn/problem/P2048
题目大意：

思路：我们考虑把所有满足条件的区间加入优先队列。显然是不可行的。
我们定义：MAX(o, l, r): max{(sum[t]-sum[o-1]), l<=t<=r}即以o为左端点，右端点范围是 [l, r]的最大子段,因为o是确定的，那么sum[o-1]也是确定的，所以求sum[t]（l<=t<=r）就可以了。这里用rmq就可以了。

我们处理出1<=o<=n的MAX(o, l, r)并且加入优先队列。那么满足条件的区间最大值一定在优先队列中，那我们ans+q.top(); q.pop(); 那么现在以o起点的可能最大区间为MAX(o, l, t-1)或者MAX(o, t+1, r)，那么把他们加入优先队列就可以了。取k次就是答案了。

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

struct RMQ{
    long long a[500005], pos[500005][20];
    void init(int n) {
        for (int i = 1; i <= n; i++) pos[i][0] = i;
        for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            int x = pos[i][j - 1], y = pos[i + (1 << (j - 1))][j - 1];
            pos[i][j] = a[x] > a[y] ? x : y;
        }
    }
    int query(int l, int r) {//区间[l, r]的最大值的下标
        int k = log2(r - l + 1);
        int x = pos[l][k], y = pos[r - (1 << k) + 1][k];
        return a[x] > a[y] ? x : y;
    }
}rmq;

struct node{
    int o, l, r, t;
    friend bool operator<(const node& a, const node& b){
        return rmq.a[a.t]-rmq.a[a.o-1]<rmq.a[b.t]-rmq.a[b.o-1];
    }
};

priority_queue<node> q;
int main(){

    int n, m, L, R;
    scanf("%d%d%d%d", &n, &m, &L, &R);
    for(int i=1; i<=n; i++){
        scanf("%lld", &rmq.a[i]);
        rmq.a[i]+=rmq.a[i-1];
    }
    rmq.init(n);
    for(int i=1; i<=n-L+1; i++){
        int l=min(n, i+L-1), r=min(n, i+R-1);
        q.push(node{i, l, r, rmq.query(l, r)});
    }
    ll ans=0;
    while(m--){
        node T=q.top(); q.pop();
        ans+=rmq.a[T.t]-rmq.a[T.o-1];
        if(T.t-1>=T.l){
            q.push(node{T.o, T.l, T.t-1, rmq.query(T.l, T.t-1)});
        }
        if(T.t+1<=T.r){
            q.push(node{T.o, T.t+1, T.r, rmq.query(T.t+1, T.r)});
        }
    }
    printf("%lld\n", ans);

    return 0 ;
}