超级钢琴

题目描述

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

输入格式

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

$N<=500,000$

$k<=500,000$

$-1000<=A~i~<=1000$

$1<=L<=R<=N$且保证一定存在满足条件的乐曲

输出格式

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

思路分析

对于音符数组$a$：$1$_____________$n$

每确定一个左端点$l$，因为区间长$len∈[L,R]$，故右端点$r∈[l+L-1,min(l+R-1,n)]：$

$1$____$l$_______$l+L-1$_____$r$______$l+R-1$____$n$

--------|<-----$L$----->|<---------$r$区间--------->|

--------|<--------------------$R$------------------->|

因此，由于$sum[l,r]=sum[r]-sum[l-1]$中，$sum[l-1]$确定，则$sum[r]$最大时，区间和$sum[i,j]$最大。

要求$sum[r]最大，r∈[l+L-1,min(l+R-1,n)]$，显然使用$ST$表

然后求出每个$l$对应的最大值，存起来，计算前$k$个，就可以了。

就可以了？

我们忽略了几个重要的点：

<1> l的可能位置有$(n-l+1)$个，也就是$(n-l+1)$个最大值，很大概率出现 $k>n-l+1$

<2> 若最大值在$[l1,r1]$区间,我们无法确定第二大值是否也在该区间

综上，我们要优化一下思路：

我们不仅要知道某区间的最大值，更重要的是知道最大值的坐标，再从最大值两侧再次查找。(这里利用了BFS的思想，体会一下)

设$t=st[i][j]$为区间$[i,i+2^j-1]$中最大值的坐标，显然最大值就是$sum[t]$;

所以，我们维护坐标的$st$表即可

由此，我们就可以求出每一个区间的和，并计算前$k$个的和了。

等等，前$k$个最值，优先队列……相当好用

写一个结构体$node$，把$node$放进优先队列。以下是几个必要的参数：

$l ->$ 固定的左端点

$r$_$l$ 和 $r$_$r ->$ 右端点范围的左右边界,即$r∈[r_l,r_r]$

$t ->$ 区间内最大值的坐标

(最后弱弱的承认，关于结构体里面的 四元组、重载 < 运算符的代码，我也贺了别人的题解)

(读书人的事，怎么能叫偷(he)呢)

$AC$代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 500100
#define endl '\n'
ll n,k,L,R;
ll a[N],st[N][20],ans;
ll sum[N];
ll askt(int l,int r)
{
    ll k=log2(r-l+1);
    ll x=st[l][k];ll y=st[r-(1<<k)+1][k];
    return sum[x]>sum[y] ? x : y;
}
struct node{
    ll l,r_l,r_r,t;
    node(){}
    node(int l,int r_l,int r_r):l(l),r_l(r_l),r_r(r_r),t(askt(r_l,r_r)){}
    friend bool operator < (const node &a,const node &b){//重载<运算符以便于优先队列的比较
        return sum[a.t]-sum[a.l-1]<sum[b.t]-sum[b.l-1];
    }
};
priority_queue<node>q;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k>>L>>R;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        st[i][0]=i;
    }
    for(ll j=1;(1<<j)<=n;j++)
        for(ll i=1;i+(1<<j)-1<=n;i++)
        {
            int a=st[i][j-1];int b=st[i+(1<<(j-1))][j-1];
            st[i][j]= sum[a]>sum[b] ? a : b;
        }
    ll num;
    for(int i=1;i+L-1<=n;i++)
    {
        q.push(node(i,i+L-1,min(i+R-1,n)));
    }
    while(k--)
    {
        node no=q.top();
        int l=no.l;int r_l=no.r_l;int r_r=no.r_r;int t=no.t;
        q.pop();
        ans+=(sum[t]-sum[l-1]);
        if(r_l!=t)  q.push(node(l,r_l,t-1));
        if(t!=r_r)  q.push(node(l,t+1,r_r));
    }
    cout<<ans<<endl;
    return 0;
}