题解 P2048 【[NOI2010]超级钢琴】

这题思路比较巧妙 首先题意是让你求前k大区间之和。 首先区间和容易想到差分。 我们枚举左端点$i$，那么右端点会有一个范围$[i + L - 1, min(i + R - 1,n)]$ 对于每个左端点，我们可以找到一个右端点，使得这段区间和最大。用堆维护所有这样的最大值，我们就能找到当前没选的区间里区间和最大的是哪个区间 因为每次要删除选过的区间，我们可以将这个左端点拆成两个，记选的数位置为k，那么在堆中加入(左端点i,右端点范围$[i+L-1,k-1]$)和(左端点i,右端点范围$[k+1, min(i + R - 1,n)])$即可 复杂度是$O(nlogn)$的啦 代码 ```cpp #include<bits/stdc++.h> #define fo(i, a, b) for (int i = (a); i <= (b); ++i) #define fd(i, a, b) for (int i = (a); i >= (b); --i) #define N 2200005 #define ls(u) t[u].s[0] #define rs(u) t[u].s[1] #define mod 51061 #define ll long long int a[N], n, m, L, R, len, st[N][23]; ll ans; inline int query (int l, int r) { len = log(r - l + 1) / log(2); return a[st[l][len]] > a[st[r - (1 << len) + 1][len]] ? st[l][len] : st[r - (1 << len) + 1][len]; } struct node{ int z, l, r, v; node (int z, int l, int r) : z(z), l(l), r(r), v(query(l, r)) {} friend bool operator < (node x, node y) {return a[x.v] - a[x.z] < a[y.v] - a[y.z];} }; std::priority_queue<node> q; int main () { scanf("%d %d %d %d", &n, &m, &L, &R); fo (i, 1, n) {scanf("%d", &a[i]); a[i] += a[i - 1]; st[i][0] = i;} fo (j, 1, 20) fo (i, 1, n) st[i][j] = a[st[i][j - 1]] > a[st[i + (1 << j - 1)][j - 1]] ? st[i][j - 1] : st[i + (1 << j - 1)][j - 1]; fo (i, 1, n) if (i + L - 1 <= n) q.push(node(i - 1, i + L - 1, std::min(i + R - 1, n))); fo (i, 1, m) { node tmp = q.top(); q.pop(); ans += a[tmp.v] - a[tmp.z]; if (tmp.v != tmp.l) q.push(node(tmp.z, tmp.l, tmp.v - 1)); if (tmp.v != tmp.r) q.push(node(tmp.z, tmp.v + 1, tmp.r)); } printf("%lld\n", ans); } ```