[NOI2010] 超级钢琴

题意

超级钢琴弹奏出 $n$ 个音符（编号 $1$ 至 $n$ ），第 $i$ 个音符美妙度为 $A_i$ （可正可负）。

超级和弦 = 编号连续的若干个音符，长度不少于 $L$ 且不多于 $R$ 。两个超级和弦相同当且仅当所含音符集合相同。

选 $k$ 个不同的超级和弦组成乐曲，使乐曲美妙度（所有超级和弦美妙度之和）最大。

$-1000 \leqslant A_i \leqslant 1000$ ， $1 \leqslant L \leqslant R \leqslant n$
保证存在满足要求的乐曲

思路

朴素做法

最直接的做法是枚举所有合法子数组，计算它们的和，排序后取前 $k$ 个：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05
 * update_at: 2026-08-05
 */
// brute.cpp：小数据暴力解，枚举所有合法超级和弦，排序取前 k 个。
#include <bits/stdc++.h>
using namespace std;

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

    int n, k, L, R;
    cin >> n >> k >> L >> R;

    vector<long long> a(n + 1), S(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        S[i] = S[i - 1] + a[i];
    }

    // 枚举所有合法超级和弦的和
    vector<long long> sums;
    for (int i = 1; i <= n; i++) {
        int left = i + L - 1;
        int right = min(i + R - 1, n);
        for (int j = left; j <= right; j++)
            sums.push_back(S[j] - S[i - 1]);
    }

    // 降序排序，取前 k 个
    sort(sums.rbegin(), sums.rend());

    long long ans = 0;
    for (int i = 0; i < k; i++)
        ans += sums[i];

    cout << ans << "\n";
    return 0;
}

这个暴力能帮助我们确认目标：本题本质上是在所有长度属于 $[L,R]$ 的连续子数组中，取出前 $k$ 大的子数组和。瓶颈也很明显：合法子数组数量是 $O(nR)$ 级别，不能全部生成再排序。

代数转化：固定左端点

连续音符序列 $[i, j]$ 的美妙度可以用前缀和表示：

Val(i, j) = S_j - S_{i-1}

如果同时让 $i$ 和 $j$ 变化，解空间是二维的。我们先固定左端点 $i$ ，此时右端点 $j$ 必须满足长度限制：

J_i = \{ j \mid i+L-1 \leqslant j \leqslant \min(n, i+R-1) \}

固定 $i$ 后， $S_{i-1}$ 是常数，最大化 $S_j - S_{i-1}$ 等价于：在区间 $J_i$ 中寻找最大的 $S_j$ 。这就把一个子数组和问题转成了 RMQ（区间最值查询）问题。

解空间分裂：从最大到次大

只求每个左端点的最大值还不够，因为题目要全局前 $k$ 大。我们把每个左端点 $i$ 对应的合法右端点区间看成一个集合，用堆维护每个集合里的当前最优解。

堆中每个状态可以理解为：

(i, l, r, pos)

$i$ ：固定的左端点
$l, r$ ：当前右端点 $j$ 的可行搜索区间
$pos$ ：区间 $[l,r]$ 中使 $S_{pos}$ 最大的下标

状态的贡献就是 $S_{pos}-S_{i-1}$ 。大根堆每次弹出的就是当前所有状态中最大的子数组和。

弹出 $(i,l,r,pos)$ 后，子数组 $(i,pos)$ 已经被选走。剩下的右端点不会消失，只是被分成两个互不相交的区间：

[l,pos-1] \quad \text{与} \quad [pos+1,r]

如果某个子区间非空，就再用 RMQ 找出这个子区间内最大的 $S_j$ ，生成新状态压回堆。这个“弹出一个最优值，再把剩余集合分裂成两个子集合”的过程，就是本题多路归并的核心。

底层组件

需要两个核心组件：

ST 表：维护前缀和数组 $S$ 的区间最大值下标。注意这里要存“下标”，不是只存最大值，因为弹出后要用这个下标 j 分裂区间。
大根堆：维护状态 Node{sum, i, j, l, r}。sum 是当前状态的最大子数组和，j 是当前区间中最优右端点，[l,r] 是还没有被消费的右端点区间。

执行流程：

计算前缀和数组 $S$ 。
建 ST 表，支持 $O(1)$ 查询区间内 $S$ 最大的位置。
对每个合法左端点 $i$ ，令初始右端点区间为 $[i+L-1, \min(n, i+R-1)]$ ，查询最优 $j$ 后入堆。
重复 $k$ 次：弹出堆顶并累加答案，再以弹出的 $j$ 为断点分裂左右区间，查询后重新入堆。

样例推演

以官方样例 $A=[3,2,-6,8]$ ， $S=[0,3,5,-1,7]$ ， $L=2, R=3$ 为例。下表展示的是堆每次弹出一个状态后，如何把它对应的右端点区间继续分裂：

步骤	堆顶状态	弹出和	区间分裂
1	$(i=1, j=2, [2,3])$	$S_2-S_0=5$	$[3,3]$ 补入
2	$(i=2, j=4, [4,4])$	$S_4-S_1=4$	无分裂
3	$(i=3, j=4, [4,4])$	$S_4-S_2=2$	无分裂

弹出 $5+4+2=11$ ，正好是样例答案。注意这里不是“每个起点只取一次”，而是某个起点的最优值被弹出后，它的剩余区间仍可能继续产生候选值。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05
 * update_at: 2026-08-05
 */
// 前缀和 + ST 表 RMQ + 堆：每次弹出当前最大子段和，分裂区间后补入次大。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
const int LOG = 20;

int n, k, L, R;
long long S[MAXN];          // 前缀和
int st[MAXN][LOG];          // ST 表存下标
int lg[MAXN];               // 预处理 log

void build_st() {
    for (int i = 1; i <= n; i++) st[i][0] = i;
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            int a = st[i][j - 1];
            int b = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = (S[a] >= S[b]) ? a : b;
        }
}

// 返回 [l, r] 中 S 值最大的下标
int query(int l, int r) {
    int j = lg[r - l + 1];
    int a = st[l][j], b = st[r - (1 << j) + 1][j];
    return (S[a] >= S[b]) ? a : b;
}

struct Node {
    long long sum;  // 该区间的最优和
    int i;          // 起始位置
    int j;          // 最优结束位置
    int l, r;       // 当前区间 [l, r]
    bool operator<(const Node& o) const { return sum < o.sum; }
};

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

    cin >> n >> k >> L >> R;
    S[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> S[i];
        S[i] += S[i - 1];
    }

    // 预处理 log
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;

    build_st();

    // 大根堆：每个起始位置维护一个最优区间
    priority_queue<Node> pq;
    for (int i = 1; i <= n; i++) {
        int l = i + L - 1;
        int r = min(i + R - 1, n);
        if (l > r) continue;
        int j = query(l, r);
        pq.push({S[j] - S[i - 1], i, j, l, r});
    }

    long long ans = 0;
    for (int t = 0; t < k; t++) {
        Node node = pq.top();
        pq.pop();
        ans += node.sum;

        // 分裂：左半 [l, j-1]
        if (node.l < node.j) {
            int jj = query(node.l, node.j - 1);
            pq.push({S[jj] - S[node.i - 1], node.i, jj, node.l, node.j - 1});
        }
        // 分裂：右半 [j+1, r]
        if (node.j < node.r) {
            int jj = query(node.j + 1, node.r);
            pq.push({S[jj] - S[node.i - 1], node.i, jj, node.j + 1, node.r});
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度

ST 表建表 $O(n \log n)$ 。每次弹出堆顶最多压入两个新状态，单次堆操作 $O(\log n)$ ，一共弹出 $k$ 次，所以堆部分为 $O(k \log n)$ 。总时间复杂度为 $O((n+k)\log n)$ 。

ST 表占用 $O(n \log n)$ 空间，堆中状态数量为 $O(n+k)$ ，总空间复杂度为 $O(n \log n)$ 。

总结

本题的核心不是 ST 表本身，而是“前缀和建模 + 固定左端点 + 区间最优值弹出后分裂”的组合模型。

看到“连续子段和 / 路径异或和”“区间长度限制 $[L,R]$ ”“求前 $K$ 大 / 前 $K$ 小”这类信号，可以优先联想到：把解空间拆成若干个集合，每个集合用数据结构快速找当前最优值，再用堆做多路归并。

《序列合并》是最基础的有序流归并；《超级钢琴》把“下一项”升级为“分裂后的子区间最优项”；《异或粽子》则把 RMQ 换成可持久化 01-Trie 查询第 $rank$ 大异或值。它们背后的主线都是：维护每一路当前最优候选，用堆取全局前 $k$ 个。

图示解析

下面这张图展示样例中每个起点的初始右端点区间，以及堆弹出后的分裂路线：

text

1
2
3
4
5
6
7
8前缀和 S:  0   3   5  -1   7
下标:      0   1   2   3   4

起始 i=1:  j∈[2,3]  S最大=5 (j=2)  → 弹出后分裂 [3,3]
起始 i=2:  j∈[4,4]  S最大=7 (j=4)  → 只有一个候选
起始 i=3:  j∈[4,4]  S最大=7 (j=4)  → 只有一个候选

堆弹出: 5(行1) → 4(行2) → 2(行3) = 11

每个起始位置对应一组右端点候选，堆维护每组当前能给出的最大子数组和。弹出一个候选后，原来的右端点区间被断点分裂，左右两边继续贡献新的候选。这样就能在不枚举所有子数组的情况下，按从大到小的顺序取出前 $k$ 个答案。

目录

题意

思路