<题解>[NOI2010]超级钢琴

洛谷题面

题目大意

给定一个整数数列,求所有子区间中区间和前k大的区间的区间和的和(绕口令?)

N\le 5\times10^5,k\le5\times10^5

分析

看到区间和,二话不说前缀和,这就没必要说了吧

然后考虑暴力:求出O(n^2)个区间的区间和,排个序什么的...或者用set动态维护...? 期望得分:...10?

然后有个很有意思的东西:k\le5\times10^5,这个东西给出来肯定不是用来凑字数的。(考场上一道类似的题,没有注意到这个东西嘤嘤嘤。不过注意到也做不出来就对了嘤嘤嘤),我们的复杂度或许与它有关...?

接下来就是优化暴力了

当我们固定了一个区间的左端点,我们再取出右边最大的一个点的值,因为\sum = S_r-S_lS_r最大,S_l固定,我们就可以知道左端点固定的情况下区间和最大的区间了。

我们考虑一个struct:< l, r_1,r_2 >,代表左端点为l,右端点区间在[r_1,r_2]的所有子区间的最大值,通过ST表加前缀和实现。我们先把每个点作为左端点,右端点区间按题意最大化以后插入一个优先队列,权值就是这个区间区间和最大的那个区间的区间和。这时候我们肯定能求出所有满足题意的子区间的区间和最大的区间了。接下来我们循环k次,每次取出堆顶,将其权值累加进入答案,然后插入两个struct(注意插入区间合法性):< l, r1, P-1 >< l,P+1,r2 >,其中P是当前struct中区间和最大的区间的右端点。k次循环完毕以后即求出了ans。

代码

这次的代码很安全

#include <cstdio>
#include <queue>
#include <algorithm>

const int N = 500000 + 10, LOGN = 20;

int n, k, L, R, s[N], st[LOGN][N], loli[N];

inline int query_rmq(int l, int r)
{
    int level = loli[r - l + 1], len = 1 << level;
    int a1 = st[level][l], a2 = st[level][r - len + 1];
    return s[a1] > s[a2] ? a1 : a2;
}

struct Node
{
    int l, r1, r2, p, v;
    Node(int l, int r1, int r2) : l(l), r1(r1), r2(r2) { p = query_rmq(r1, r2), v = s[p] - s[l - 1]; }
    inline bool operator<(const Node &b) const { return v < b.v; }
};

std::priority_queue<Node> q;

inline void rmq(void)
{
    loli[0] = -1;
    for (int i = 1; i <= n; ++i)
        loli[i] = loli[i >> 1] + 1;
    for (int i = 1; i <= n; ++i)
        st[0][i] = i;
    for (int i = 1, ii = 1; i != LOGN; ++i, ii <<= 1)
        for (int j = 1; j <= n; ++j)
            st[i][j] = s[st[i - 1][j]] > s[st[i - 1][j + ii]] ? st[i - 1][j] : st[i - 1][j + ii];
}

int main(void)
{
    scanf("%d %d %d %d", &n, &k, &L, &R);
    for (int i = 1; i <= n; ++i)
        scanf("%d", s + i), s[i] += s[i - 1];
    rmq();
    for (int i = 1; i + L - 1 <= n; ++i)
        q.push(Node(i, i + L - 1, std::min(n, i + R - 1)));
    long long ans = 0;
    while(k--)
    {
        Node p = q.top();
        q.pop();
        ans += p.v;
        if (p.p != p.r1)
            q.push(Node(p.l, p.r1, p.p - 1));
        if (p.p != p.r2)
            q.push(Node(p.l, p.p + 1, p.r2));
    }
    printf("%lld", ans);
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注