quhengyi11 的博客

quhengyi11 的博客

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

posted on 2018-12-13 22:23:43 | under 题解 |

这题思路比较巧妙

首先题意是让你求前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)$的啦

代码

#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);
}