P2048 [NOI2010] 超级钢琴

题意

在一个数组中选择 \(k\) 个长度为 \([l, r]\) 的序列，对每个序列求和，使每个序列的和的和最大。

思路

首先，我们可以将序列之和转化为前缀和，如果固定左端点 \(l\)，那么我们只需要在 \([l + len_l, l + len_r]\) 中寻找最大的右端点，减去 \(sum[l - 1]\) 就是在长度为 \([len_l, len_r]\) 左端点为 \(l\) 的序列的最大值，这个可以用 ST 表实现。

然后，对于每次决策，我们都选择最大的那个和弦加入答案，这个我们可以用优先队列实现。假设我们选择的是以 \(l\) 为左端点，长度为 \([len_l, len_r]\) 的区间，选择的有端点为 \(r\)，那么我们还需要将 \({l, len_l, r - 1}\) 和 \({l, r + 1, len_r}\) 放入优先队列，进行比较。

代码

注意开 long long。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int N = 500010, K = 500010;

int n, k, l, r;
i64 a[N], sum[N], st[20][N];

void initst() {
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            int p1 = st[j - 1][i], p2 = st[j - 1][i + (1 << j - 1)];
            if (sum[p1] < sum[p2]) st[j][i] = p2;
            else st[j][i] = p1;
        }
    }
}

int query(int l, int r) {
    int len = r - l + 1;
    int lg = __lg(len);
    int p1 = st[lg][l], p2 = st[lg][r - (1 << lg) + 1];
    if (sum[p1] < sum[p2]) return p2;
    else return p1;
}

struct node {
    int l, r_l, r_r;
};

pair<i64, int> getans(const node& a) {
    int q = query(a.r_l, a.r_r);
    i64 ans = sum[q] - sum[a.l - 1];
    return {ans, q};
}

bool operator<(const node& a, const node& b) {
    return getans(a) < getans(b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k >> l >> r;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        st[0][i] = i;
    }

    initst();

    priority_queue<node> q;
    for (int i = 1; i + l - 1 <= n; i++) q.push({i, i + l - 1, min(n, i + r - 1)});
    
    i64 ans = 0;
    for (int i = 1; i <= k; i++) {
        node t = q.top();
        q.pop();

        pair<i64, int> q_t = getans(t);
        ans += q_t.first;

        if (q_t.second > t.r_l) q.push({t.l, t.r_l, q_t.second - 1});
        if (q_t.second < t.r_r) q.push({t.l, q_t.second + 1, t.r_r});
    }
    cout << ans << '\n';
    return 0;
}