P2048 NOI2010 超级钢琴

很好的一道RMQ题

题面

NOI2010 超级钢琴

题目描述

小 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

样例输入 #1

4 3 2 3
3
2
-6
8

样例输出 #1

11

提示

样例解释

共有 $5$ 种不同的超级和弦：

1. 音符 $1 \sim 2$，美妙度为 $3+2=5$；
2. 音符 $2 \sim 3$，美妙度为 $2+(-6)=-4$；
3. 音符 $3 \sim 4$，美妙度为 $(-6)+8=2$；
4. 音符 $1 \sim 3$，美妙度为 $3+2+(-6)=-1$；
5. 音符 $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$ 且保证一定存在满足要求的乐曲。

---

思路

先想想怎么暴力：

把每种可能的情况都枚举出来，然后丢到一个优先队列里，拿出前$k$个。

对于区间长度，一个一个地加可不是一个好办法，可以用前缀和优化。

---

反思上述过程，实际上就是枚举每个左端点，右端点在一定范围内找到一个区间使区间和更大。

而区间$[o,p]$的区间和为sum[p]-sum[o-1]，对于枚举的o为左端点是确定的即sum[o-1]是确定的；

右端点在区间$[l,r]$的范围内，使sum[p]最大，那么这段区间和也就最大。

求某段区间某个元素的最大值？

• RMQ

设求出的最大右端点为$p$（$p$作为sum数组的下标，比较依据是前缀和，储存的是下标），

每求出一个$[o,p]$的最优区间，就把它丢到优先队列里，这里需要一个结构体来储存区间信息，虽然对于$o$这个左端点来说$p$这个右端点是最优的，但是在$[l,r]$范围内一定存在次优，次次优的右端点，而这些区间可能会比其它的左端点的最优解还优，因此还需要把剩下的右端点范围也放入考虑范围。

因此，这个结构体需要存储四个信息：

• 左端点$o$
• 右端点的$l$
• 右端点的$r$
• 在$[l,r]$范围内最优右端点$p$

若$p$刚好为$l$或$r$，则需要特判一下；

PUSH:

if(l!=p) Q.push(range(o,l,p-1));
   if(r!=p) Q.push(range(o,p+1,r));

range结构体:

struct range
{
    int l,r,o,p;
    range(){}
    range(int _o,int _l,int _r){l=_l;r=_r;o=_o;p=qe(_l,_r);}//o是左端点，l~r为右端点范围，p为最优右端点下标
    bool operator < (const range &a) const
    {
        return sum[p]-sum[o-1]<sum[a.p]-sum[a.o-1];
    }
};

这其实是一个贪心的过程，我们先把所有初始区间加入到堆中，然后每次取出最大累加答案的并将它的附属区间加入进行比较，复杂度$O(n+logk)$。

预处理复杂度为$nlogn$，查询$k$次，总复杂度:$O(n+k+nlogn+logk)$

注意要开long long

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+7;
int sum[N];
int st[N][23];
int n,k,l,r,ans;
void init()
{
    for(int i=1;i<=n;i++)
        st[i][0]=i;//存下标
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)//求区间前缀和最大值的下标
            st[j][i]=sum[st[j][i-1]]>sum[st[j+(1<<(i-1))][i-1]]?st[j][i-1]:st[j+(1<<(i-1))][i-1];
}
int qe(int l,int r)
{
    int k=(int)log2(r-l+1);//返回最大前缀和的下标
    int x=st[l][k],y=st[r-(1<<k)+1][k];
    return sum[x] > sum[y] ? x : y;
}
struct range
{
    int l,r,o,p;
    range(){}
    range(int _o,int _l,int _r){l=_l;r=_r;o=_o;p=qe(_l,_r);}//o是左端点，l~r为右端点范围，p为最优右端点下标
    bool operator < (const range &a) const
    {
        return sum[p]-sum[o-1]<sum[a.p]-sum[a.o-1];
    }
};
priority_queue<range> Q;
signed main()
{
    scanf("%lld%lld%lld%lld",&n,&k,&l,&r);
    for(int i=1;i<=n;i++)
        scanf("%lld",&sum[i]),sum[i]+=sum[i-1];
    init();
    for(int i=1;i<=n;i++)
    {
        if(i+l-1<=n)
            Q.push(range(i,i+l-1,min(i+r-1,n)));
    }
    while(k--)
    {
        int o=Q.top().o,l=Q.top().l,r=Q.top().r,p=Q.top().p;
        Q.pop();
        ans+=sum[p]-sum[o-1];
        if(l!=p) Q.push(range(o,l,p-1));
        if(r!=p) Q.push(range(o,p+1,r));
    }
    printf("%lld",ans);
    return 0;
}