题解：P2048 [NOI2010] 超级钢琴【思维贪心+数据结构】
ylch
·
2025-08-29 16:54:17
·
题解
发现区间不定长，这就很讨厌。
暴力
考虑对于每个以 i 为左端点的区间，因为长度范围 [L,R] ，所以右端点范围为 [i+L-1,i+R-1] 。
不难想到区间和可以用前缀和数组 s 来快速取得。
考虑暴力存储所有的区间和再排序，时间复杂度可以达到 O(n^2 \log n) 。
正解
书接上回，考虑对于每个以 i 为左端点的区间，如果只取一次，那么它能取到的最大值应该是 \max\{s[x]\} - s[i-1],\ x \in [i+l-1,i+r-1] 。发现每个 s[x] 都必须减去 s[i-1] ，那么比大小就成了纯比较 s[x] 。不难想到可以用 ST 表维护任意区间中的最大前缀和以及位置（代码实现得很妙）。
现在我们能快速取得最值信息了，下面就思考贪心策略：怎样取最优？
首先对于最大美妙度，如果把之前预处理出来的每个 i 的信息都放到大根堆里，那么排序后堆顶肯定就是最大的。
那第二大呢？我们可以破开 最大的，假设最大值的前缀和为 s_t ，将原本的 [i,t] 删掉，再把 [i,(i+L-1) \sim (t-1)] 和 [i, (w+1) \sim (i+R-1)] 中的最大值入堆。
破开依据：“两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的”。
那这样贪心为什么是对的呢？好像很显然。 因为一个 i 为左端点的最大值摘出去后，i 可能还会作为其他有用值的左端点，所以再放回去就很对。
这样就解决了，考虑把状态 (i,l,r,t) 表示左端点为 i ，右端点可以在 [l,r] 范围内，前缀和最大值的下标为 t 。
---
**这种问题的通法：建立集合 $S$，使当前剩余最大值一定存在于 $S$ 中，且使得将最大值排除后，集合性质不变。**
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 7;
int n, k, L, R, st[maxn][30]; // 这里的st中存的是最大前缀和的下标
ll s[maxn];
void init(){
for(int i = 1; i <= n; i ++) st[i][0] = i;
for(int j = 1; j <= log2(n); j ++){
for(int i = 1; i + (1 << j) - 1 <= n; i ++){
int a = st[i][j - 1], b = st[i + (1 << (j - 1))][j - 1];
st[i][j] = s[a] > s[b]? a : b; // 比较值的大小，存下标即可
}
}
}
int query(int l, int r){
int k = log2(r - l + 1);
int a = st[l][k], b = st[r - (1 << k) + 1][k];
return s[a] > s[b]? a : b;
}
struct Node{
int i, l, r, t;
bool operator < (Node p) const{
return s[t] - s[i - 1] < s[p.t] - s[p.i - 1]; // 注意堆默认大顶堆，这里重载是小于号，排序规则反过来
}
};
priority_queue<Node> Q;
void solve(){
cin >> n >> k >> L >> R;
for(int i = 1; i <= n; i ++){
cin >> s[i]; s[i] += s[i - 1]; // 直接输入前缀和数组即可
}
init();
for(int i = 1; i + L - 1 <= n; i ++){
int l = i + L - 1, r = min(n, i + R - 1);
Q.push({i, l, r, query(l, r)});
}
ll ans = 0;
while(k --){
auto [i, l, r, t] = Q.top(); Q.pop();
ans += s[t] - s[i - 1];
if(l != t) Q.push({i, l, t - 1, query(l, t - 1)});
if(r != t) Q.push({i, t + 1, r, query(t + 1, r)}); // 破开当前元素，重新放入堆中
}
cout << ans << '\n';
}
signed main(){
ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
return 0;
}
```