[NOI2010]超级钢琴【RMQ+贪心+堆】

题目链接

  超级棒的一道题，解这道题，需要分一下几步来看。

1. 取的是连续段
2. 我们可以对每个可能起点去知道它的最大可能解（起点begin，最大可行解一定是begin + L - 1 ~ begin + R - 1中的一个）
3. 如果每次都是取最大的话，那么下一个同起点的一定是不大于它的，贪心思想

既然提出了问题，我们逐步解决：

对于提出的问题一，可以使用前缀和来减少每次查询带来的不方便；

对于问题二，因为确定了起点begin，找到在可行解区间内的最大解，一定是可以用数据结构求区间最大值来做到的，这里要求的是最大值对应的点。于是就可以确定每个起点的最大解了。这里用的是RMQ，因为没有修改操作。

对于问题三，我们可以把问题二处理出来的东西，放进堆（优先队列），每次弹出最大的，然后在把点的可行区间变成begin + L - 1 ~ pos - 1和pos + 1 ~ begin + R - 1这两个区间，然后以此类推。那么，堆内的元素最多N+2K个，所以内存也是够的，每次用一次RMQ，查询复杂度O（1）。

总结：思维好题。RMQ千万别写错了hh

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
//#include <unordered_map>
//#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define eps 1e-8
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 5e5 + 5;
int N, K, L, R, a[maxN], sum[maxN] = {0}, LOG_2[maxN], mp[maxN][21];
inline void RMQ_Init()
{
    for(int i=1; i<=N; i++) mp[i][0] = i;
    for(int j=1; (1 << j) <= N; j++)
    {
        for(int i=1; i + (1 << (j - 1)) <= N; i++)
        {
            if(sum[mp[i][j - 1]] >= sum[mp[i + (1 << (j - 1))][j - 1]]) mp[i][j] = mp[i][j - 1];
            else mp[i][j] = mp[i + (1 << (j - 1))][j - 1];
        }
    }
}
inline int query(int ql, int qr)
{
    int det = LOG_2[qr - ql + 1];
    return sum[mp[ql][det]] >= sum[mp[qr - (1 << det) + 1][det]] ? mp[ql][det] : mp[qr - (1 << det) + 1][det];
}
struct node
{
    int beg, ql, qr, pos, val;
    node(int a=0, int b=0, int c=0, int d=0, int f=0):beg(a), ql(b), qr(c), pos(d), val(f) {}
    friend bool operator < (node e1, node e2) { return e1.val < e2.val; }
} now;
priority_queue<node> Q;
inline void init()
{
    for(int i = 1, j = 2, k = 0; i <= N; i++)
    {
        if(i == j) { j <<= 1; k++; }
        LOG_2[i] = k;
    }
}
int main()
{
    scanf("%d%d%d%d", &N, &K, &L, &R);
    init();
    sum[0] = 0;
    for(int i=1; i<=N; i++) { scanf("%d", &a[i]); sum[i] = sum[i - 1] + a[i]; }
    RMQ_Init();
    int ql, qr, pos, nex_pos;
    for(int i=1; i + L - 1 <= N; i++)
    {
        ql = i + L - 1; qr = min(i + R - 1, N);
        pos = query(ql, qr);
        Q.push(node(i, ql, qr, pos, sum[pos] - sum[i - 1]));
    }
    ll ans = 0;
    while(K--)
    {
        now = Q.top(); Q.pop();
        ans += now.val;
        ql = now.ql; qr = now.qr; pos = now.pos;
        if(pos - 1 >= ql)
        {
            nex_pos = query(ql, pos - 1);
            Q.push(node(now.beg, ql, pos - 1, nex_pos, sum[nex_pos] - sum[now.beg - 1]));
        }
        if(pos + 1 <= qr)
        {
            nex_pos = query(pos + 1, qr);
            Q.push(node(now.beg, pos + 1, qr, nex_pos, sum[nex_pos] - sum[now.beg - 1]));
        }
    }
    printf("%lld\n", ans);
    return 0;
}