「解题报告」超级钢琴 - APJifengc的博客

题目传送门： P2048

题目描述

小 Z 是一个小有名气的钢琴家，最近 C 博士送给了小 Z 一架超级钢琴，小 Z 希望能够用这架钢琴创作出世界上最美妙的音乐。这架超级钢琴可以弹奏出 $n$ 个音符，编号为 $1$ 至 $n$。第 $i$ 个音符的美妙度为 $A_i$，其中 $A_i$ 可正可负。一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于 $L$ 且不多于 $R$。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。小 Z 决定创作一首由 $k$ 个超级和弦组成的乐曲，为了使得乐曲更加动听，小 Z 要求该乐曲由 $k$ 个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小 Z 想知道他能够创作出来的乐曲美妙度最大值是多少。

输入格式

输入第一行包含四个正整数 $n,k,L,R$。其中 $n$ 为音符的个数，$k$ 为乐曲所包含的超级和弦个数，$L$ 和 $R$ 分别是超级和弦所包含音符个数的下限和上限。接下来 $n$ 行，每行包含一个整数 $A_i$，表示按编号从小到大每个音符的美妙度。

输出格式

输出只有一个整数，表示乐曲美妙度的最大值。

输入输出样例

输入 #1
4 3 2 3
3
2
-6
8
输出 #1
11
说明/提示

样例解释

共有 555 种不同的超级和弦：

音符 $1 \sim 2$，美妙度为 $3+2=5$；

音符 $2 \sim 3$，美妙度为 $2+(−6)=−4$；

音符 $3 \sim 4$，美妙度为 $(−6)+8=2$；

音符 $1 \sim 3$，美妙度为 $3+2+(−6)=−1$；

音符 $2 \sim 4$，美妙度为 $2+(−6)+8=4$。最优方案为：乐曲由和弦 $1,3,5$ 组成，美妙度为 $5+2+4=11$。
所有数据满足：$-1000 \leq A_i \leq 1000$，$1 \leq L \leq R \leq n$ 且保证一定存在满足要求的乐曲。

思路

首先，题目要求区间和的最大值，既然求区间和，我们不妨考虑一下使用前缀和优化。

设 $pre_i$ 为 $A_1+\cdots+A_i$ ，那么 $A_i+\cdots+A_j$ 等于 $pre_j-pre_{i-1}$ 。

我们可以首先枚举区间的左端点（设为 $p$ ），此时 $pre_{i-1}$ 是固定的，我们只需要使 $pre_j$ 最大，那么这个区间的和就是最大的。

因为一段超级和弦的长度必须在 $l\sim r$，所以问题就转化为了在 $i+l-1\le j\le i+r-1$ 的范围内，寻找一个最大的 $pre_j$ 。

这是一个 $\mathrm{RMQ}$ 问题， $pre$ 不变，而我们需要较快的查询，所以我们可以考虑使用 $\mathrm{ST}$表来解决这个问题。

这样，我们就可以求出以 $p$ 为左端点，使 $p\sim q$ 的区间和最大的右断点 $q$。

那么我们求出了一个最大的区间和之后呢？

题目要求求出 $k$ 个区间的和的最大值，那么我们可以考虑取 $k$ 次区间最大值，这样这 $k$ 个区间的和就是最大的。

我们可以将每一个左端点能够组成的一个区间扔进一个堆里，每一次取区间和最大的。

那么假如我们取出了 $p\sim q$ 这样一个区间之后，如何处理剩余的以 $p$ 为左端点的区间呢？

我们知道， $q$ 一定是在 $p+l-1$ 与 $p+r-1$ 中取出的，那么取出 $q$ 后，我们只需要再去找 $p+l-1\sim q-1$ 与 $q+1\sim p+r-1$ 两个区间中作为右端点的区间和最大值即可。

不妨设这样一个四元组： $(p,q,l,r)$ 代表以 $p$ 为左端点，右端点在 $l\sim r$ 区间内，且当右端点为 $q$ 时区间和最大。

我们可以首先枚举 $p,l,r$ ，然后计算出 $q$ ，再把它扔进一个堆里，按照区间和的大小排序。

每一次取出一个四元组 $(p,q,l,r)$ 后，我们再将 $(p,q_1,l,q-1)$ 与 $(p,q_2,q+1,r)$ 放入堆中（$q_1$ 与 $q_2$ 可以直接求出来），这样重复取 $k$ 次，就是这道题的答案了。

注意/提示

$i+r-1$ 不可以超过 $n$ ，所以在枚举时右端点可以枚举 $\min(i+r-1,n)$。
$q$ 有可能在 $l,r$ 的边界上，此时有一个区间是不存在的，要特殊判断。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005, LOG = 20;
int pre[MAXN], a[MAXN], st[MAXN][LOG], Log[MAXN], n, k, l, r;
void init() { // 预处理ST表
    Log[1]=0; for(int i=2;i<=n;i++) Log[i]=Log[i/2]+1;
    for(int i=1;i<=n;i++) st[i][0]=i;
    for(int j=1;j<=Log[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]=pre[a]>pre[b]?a:b;
        }
    }
}
int RMQ(int l,int r) { // 求pre的区间最大值
    int len=Log[r-l+1];
    int a=st[l][len],b=st[r-(1<<len)+1][len];
    return pre[a]>pre[b]?a:b;
}
struct Answer { // 四元组
    int p,l,r,q;
    Answer(int p,int l,int r):p(p),l(l),r(r) {
        q=RMQ(l,r); // 通过p,l,r求出q
    }
    int getValue() const { return pre[q]-pre[p-1]; } // 求区间和
    friend bool operator<(const Answer &a, const Answer &b) { // 重载运算符
        return ((a.getValue()) < (b.getValue()));
    }
};
priority_queue<Answer> q;
long long ans=0;
int main() {
    scanf("%d%d%d%d", &n, &k, &l, &r);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
    init();
    for(int i=1;i+l-1<=n;i++) q.push(Answer(i,i+l-1,min(i+r-1, n)));
    for(int i=1;i<=k;i++) {
        Answer t = q.top(); q.pop();
        ans+=t.getValue();
        if (t.q!=t.l) q.push(Answer(t.p,t.l,t.q-1));
        if (t.q!=t.r) q.push(Answer(t.p,t.q+1,t.r));
    }
    printf("%lld\n", ans);
    return 0;
}