题目描述

小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。

这架超级钢琴可以弹奏出 $n$ 个音符，编号为 $1$ 至 $n$ 。第 $i$ 个音符的美妙度为 $A_i$ ，其中 $A_i$ 可正可负。

一个“超级***”由若干个编号连续的音符组成，包含的音符个数不少于 $L$ 且不多于 $R$ 。我们定义超级***的美妙度为其包含的所有音符的美妙度之和。两个超级***被认为是相同的，当且仅当这两个超级***所包含的音符集合是相同的。

小Z决定创作一首由k个超级***组成的乐曲，为了使得乐曲更加动听，小Z要求该乐曲由k个不同的超级***组成。我们定义一首乐曲的美妙度为其所包含的所有超级***的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。

输入输出格式

输出格式

输入第一行包含四个正整数 $n,k,L,R$ 。其中 $n$ 为音符的个数， $k$ 为乐曲所包含的超级***个数， $L$ 和 $R$ 分别是超级***所包含音符个数的下限和上限。

接下来 $n$ 行，每行包含一个整数 $A_i$ ，表示按编号从小到大每个音符的美妙度。

输入格式

输出只有一个整数，表示乐曲美妙度的最大值。

输入输出样例

输入样例

输出样例

说明

1.    音符1 ~ 2，美妙度为3 + 2 = 5
2.    音符2 ~ 3，美妙度为2 + (-6) = -4
3.    音符3 ~ 4，美妙度为(-6) + 8 = 2
4.    音符1 ~ 3，美妙度为3 + 2 + (-6) = -1
5.    音符2 ~ 4，美妙度为2 + (-6) + 8 = 4

最优方案为：乐曲由***1，***3，***5组成，美妙度为5 + 2 + 4 = 11。

数据范围

所有数据满足： $-1000 \leq A_i \leq 1000, 1 \leq L \leq R \leq n$ 且保证一定存在满足要求的乐曲。

题目链接

思路

暴力解法

整理一下这个题的题意，其实就是求序列长度在 $[l, r]$ 范围内的的前 $k$ 大序列的和。

最暴力的想法当然是枚举序列的长度，然后枚举端点，再维护一个记录前k大序列值的数组，每次求到一个新的序列和，暴力更新。

既然是最暴力的想法，当然可以优化，而这道题优化之后就能得到正解。

优化

优化一

既然是求序列长度和，聪明的你有没有想到什么奇技淫巧呢？

这...这不是前缀和吗？

我们可以预处理一个前缀和的数组，这样知道长度和端点之后就可以 $O(1)$ 地求序列和了。

优化二

暴力解法中，有提到枚举区间长度和端点对吧？

我们可以进行另一个优化。

先枚举左端点，这样我们就可以根据左端点的下标和给出的 $l, r$ 来求出右端点的范围了。

根据前缀和的定义，已知左端点之后，只需要最大化从 $1$ 到右端点的前缀和即可。

然而我们已经知道右端点的范围了，那么这就是一个 $RMQ$ 问题。可以用代码简单的 $ST$ 表来解决这个问题，只需进行 $O(n \log_2(n))$ 复杂度的预处理，即可进行 $O(1)$ 时间复杂度的查询。 <del>你非要写线段树也不拦着你。 </del>

优化三

对于每次通过枚举端点求出的序列，定义一个四元组 $(s, t, l, r)$ , $s, t$ 分别表示左右端点的下标， $l, r$ 表示右端点的范围。

现在的暴力算法，只剩下求前 $k$ 大的序列这个操作没有优化过了。实际上，动态求前 $k$ 大，堆这种数据结构是再方便不过了，况且 $C++$ 的 $STL$ 库里还有优先队列这种方便的东西。

利用堆以区间长度为关键字，在堆中维护这些四元组。此时的堆为大根堆。

整理

这样的话，先枚举序列的，再利用求在右端点范围内的前缀和最大值，再用堆维护优化三中提到的四元组。

然后，边弹出堆顶，边插入新的四元组 $(s, summax(l, t - 1), l, t - 1)$ 和 $(s, summax(t + 1, r), t + 1, r)$ 。其中 $max$ 表示区间内前缀和最大的端点的下标。因为如果不插入的话只是以每个点为左端点求最大值，然而这 $k$ 个序列的左端点可以重复，所以需要把这个右端点扣掉后再压入堆。弹出堆顶 $k$ 次，和即为答案。这一步

代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <cstring>
#include <queue>
#define DEBUG(x) std::cerr << #x << " = " << x << endl

const int MAXN = 500000 + 7;

int f[MAXN][22], sum[MAXN];
int n, k, L, R;
long long ans;

struct Node {
    int s, l, r, t;

    bool operator < (const Node &x) const {
        return sum[t] - sum[s - 1] < sum[x.t] - sum[x.s - 1];
    }
};

std::priority_queue<Node> heap;

inline int mx(int x, int y) {
    return sum[x] > sum[y] ? x : y;
}

inline int query(int l, int r) {
    if(l > r) return -1;
    int k = std::log(r - l + 1) / std::log(2);
    return mx(f[l][k], f[r - (1 << k) + 1][k]);
}

int main(int argc, char *argv[]) {
    scanf("%d %d %d %d", &n, &k, &L, &R);
    int w;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w);
        sum[i] = sum[i - 1] + w;
        f[i][0] = i;
    }
    for (int j = 1; j <= 19; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[i][j] = mx(f[i][j - 1],  f[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 1; i + L - 1 <= n; i++) {
        int right = std::min(n, i + R - 1);
        heap.push((Node) {i, i + L - 1, right, query(i + L - 1, right)});
    }
    int cnt = 0;
    while (cnt < k) {
        cnt++;
        Node g = heap.top(); heap.pop();
        ans += sum[g.t] - sum[g.s - 1];
        int q1 = query(g.l, g.t - 1);
        int q2 = query(g.t + 1, g.r);
        if(~q1) heap.push((Node) {g.s, g.l, g.t - 1, q1});
        if(~q2) heap.push((Node) {g.s, g.t + 1, g.r, q2});
    }
    printf("%lld\n", ans);
    return 0;
}

【NOI2010】超级钢琴【题解】