算法标签

前缀和、ST表（稀疏表）、优先队列（堆）、贪心

问题分析

我们需要从所有长度在 $[L, R]$ 之间的连续音符子数组（超级和弦）中，选出 $k$ 个不同的子数组，使得它们的美妙度之和最大。

关键观察

1. 连续子数组的美妙度可以用前缀和快速计算：子数组 $[i, j]$ 的美妙度为 $pre[j]-pre[i-1]$（其中 $pre$ 是前缀和数组）。
2. 对于每个左端点 $i$，合法的右端点范围是 $[i+L-1, i+R-1]$，我们需要在这个范围内找到使 $pre[j]-pre[i-1]$ 最大的 $j$，并通过贪心和堆结构来选择前 $k$ 大的子数组。

核心算法思路

1. 前缀和与ST表预处理

• 计算前缀和数组 $pre$，用于快速得到任意子数组的和。
• 构建ST表（稀疏表），用于在 $O(1)$ 时间内查询区间 $[l, r]$ 内使 $pre[j]$ 最大的位置 $j$，从而快速得到以 $i$ 为左端点的最优右端点。

2. 优先队列（堆）的贪心选择

• 对于每个左端点 $i$，确定其合法右端点范围 $[L_i, R_i]$（$L_i = i+L-1$，$R_i = i+R-1$），并找到该范围内使 $pre[j]-pre[i-1]$ 最大的 $j$，将该子数组的信息（左端点、右端点范围、最优位置、美妙度）存入大根堆。
• 每次从堆中取出当前最大的子数组，累加到答案中。然后将该子数组的“左半部分”（$[L_i, j-1]$）和“右半部分”（$[j+1, R_i]$）的最优子数组信息重新插入堆中，确保后续能选择到次大的子数组。

3. 时间复杂度分析

• ST表预处理：$O(n \log n)$。
• 初始入堆操作：$O(n)$（每个左端点入堆一次）。
• 堆操作：每次堆操作是 $O(\log n)$，共进行 $k$ 次，总时间 $O(k \log n)$。
• 整体时间复杂度为 $O(n \log n + k \log n)$，可满足题目中 $n \leq 5 \times 10^5$、$k \leq 5 \times 10^5$ 的数据范围。

总结

本题通过前缀和快速计算子数组和，ST表快速查询区间最大值位置，结合优先队列（堆）的贪心策略，高效地选出了 $k$ 个最大的不同超级和弦，从而得到乐曲的最大美妙度。这种方法充分利用了数据结构的特性，在时间和空间复杂度上都能满足题目要求。