题解 [NOI2010]超级钢琴

终于更博了,之前有点摆

题目

题意:

有一个长为 (n) 的数列 (A) ,定义区间 ([i, j]) 的权值为 (sum_{k=i}^j A_k)

现在选出 (k) 个不相同的区间,使得它们的权值和最大. 并满足每个选出的区间长度∈([L, R])

暴力 (n^2) 不说了,讲正解.

正解:

快速求出"区间集" ((p,l,r)) 的最大答案(下文中会对此有解释)

首先区间 ([l,r]) 的答案为 (sum[r]-sum[l-1]) .

那么如何确保区间长度 (r-l+1in [L,R]) 呢?

显然,对于一个确定的左端点 (i) ,它的右端点的取值范围是 ([i+L-1,i+R-1]) .

在这 (R-L+1) 个左端点为 (i) 的区间中,如何选出区间和最大的呢?

对于每一个区间,其区间和为 (sum[j]-sum[i]space(jin[i+L-1,i+R-1]))

其中 (sum[i]) 为定值,那么问题转换为求 (sum[i]space(jin[i+L-1,i+R-1])) 的最值

既然是(RMQ) (区间最值) 那么就可以用ST表来维护,每次可以 (Theta(1)) 求解.

那么现在,我们可以求出区间集 {([l,r])} (space(rin[l+L-1,l+R-1])) 中的最大区间.

用一个三元组 ((p,l,r)) 来表示一个左端点为(p),右端点属于([l,r]) 区间集 (S).

如何做到答案覆盖整个区间不遗漏

先以每个位置为左端点构造(n) 个三元组,注意边界.

同时对每个三元组记录出它的答案,以及取到最大值区间时的右端点位置(这个位置可以预处理倍增数组).

把它们丢到堆里面,每次取出最大的弹掉,进行(k)次.

其中要注意的是在弹掉一个三元组 ((p,l,r)) 后,就意味着去掉了所有的区间 ([p,i]space(iin[l,r]))

然而实际上我们只取出了一个区间 ((p,mid)) ((mid) 即为"取到最大值区间时的右端点位置").

所以还要保留区间 ([p,i]space(iin[l,mid-1])) 以及 ([p,i]space(iin[mid+1,r])) 的答案.

所以将这两个东西加入堆中,并且要算出它们的 (mid) .

跑 (k) 次就可以了.

代码:

#include<bits/stdc++.h>
#define il inline 
#define RG register int
#define ll long long
#define gc getchar
using namespace std;
il int rd()
{
    RG x=0,flag=1;
    char ch=0;
    while((ch>'9'||ch<'0')&&ch!='-')ch=gc();
    if(ch=='-')flag=-1,ch=gc();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=gc();
    return x*flag;
}
const int N=500005,LOG=22;
ll f[N][LOG],sum[N];
int pos[N][LOG],Log[N];
ll Ans;
int n,k,L,R;
ll query(int l0,int r0)
{
    int t=Log[r0-l0+1];
    return max(f[l0][t],f[r0-(1<<t)+1][t]);
}
int query2(int l0,int r0)
{
    int t=log2(r0-l0+1);
    return f[l0][t]>f[r0-(1<<t)+1][t]?pos[l0][t]:pos[r0-(1<<t)+1][t];
}
struct node {
    int p,l,r,mid; ll res;
    bool operator <(node x)const {return res<x.res;}
};
priority_queue<node> q; 
int main ()
{
    scanf("%d%d%d%d",&n,&k,&L,&R);
    int LogN=log2(n)+1;
    for(RG i=1;i<=n;i++)sum[i]=sum[i-1]+rd();
    Log[0]=-1;
    memset(f,0xcf,sizeof(f));
    for(RG i=1;i<=n;i++) f[i][0]=sum[i],pos[i][0]=i,Log[i]=Log[i>>1]+1;
    for(RG j=1;j<=LogN;j++) 
        for(RG i=1;i+(1<<j)<=n+1;i++) 
        {
            if(f[i][j-1]>f[i+(1<<j-1)][j-1])
            {
                f[i][j]=f[i][j-1];
                pos[i][j]=pos[i][j-1];
            }
            else
            {
                f[i][j]=f[i+(1<<j-1)][j-1];
                pos[i][j]=pos[i+(1<<j-1)][j-1];
            }
        }
    for(RG i=1;i+L-1<=n;i++)
    {
        ll t=query(i+L-1,min(i+R-1,n))-sum[i-1];
        int midt=query2(i+L-1,min(n,i+R-1));
        q.push(node{i,i+L-1,min(i+R-1,n),midt,t});//
    }
    for(RG i=1;i<=k;i++)
    {
        Ans+=q.top().res;
        node t=q.top();
        int p0=t.p,l0=t.l,r0=t.r,mid0=t.mid;
        q.pop();
        if(mid0>l0)
            q.push(node{p0,l0,mid0-1,query2(l0,mid0-1),query(l0,mid0-1)-sum[p0-1]});
        if(mid0<r0)
            q.push(node{p0,mid0+1,r0,query2(mid0+1,r0),query(mid0+1,r0)-sum[p0-1]});
    }
    cout<<Ans<<endl;
    return 0;
}