P2048 [NOI2010] 超级钢琴

经典题。

需要求出前 $k$ 大的长度在 $[l,r]$ 之间的子段和。需要考虑如何删去已经选过的子段。将每个点 $p$ 单独对应一个候选区间 $[l_p,r_p]$，设 $x$ 该区间中的最优解的位置贡献为 $sum[x]-sum[p-1]$，$sum[]$ 为原数组前缀和，$x$ 可以通过 ST 表查询区间最大值的位置得到。选取之后考虑将候选区间 $[l_p,r_p]$ 分为 $[l_p,x-1]$ 和 $[x+1,r_p]$，这样就不会取到重复的区间了。整个过程用优先队列来维护，选 $k$ 次即可。时间复杂度 $\mathcal O(n\log n+k\log n)$。

Code

#include<iostream>
#include<cstdio>
#include<queue>
#define ll long long
using namespace std;
const int N=5e5+10,K=21;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,k,l,r;
int sum[N];
int st[N][K];
int Log[N];
struct Node
{
    int p,l,r,x;
    bool operator<(const Node &t)const{return sum[x]-sum[p-1]<sum[t.x]-sum[t.p-1];}
};
priority_queue<Node>q;

inline void build()
{
    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++)
            sum[st[i][j-1]]>=sum[st[i+(1<<j-1)][j-1]]?st[i][j]=st[i][j-1]:st[i][j]=st[i+(1<<j-1)][j-1];
}
inline int query(int l,int r)
{
    int t=Log[r-l+1];
    return sum[st[l][t]]>=sum[st[r-(1<<t)+1][t]]?st[l][t]:st[r-(1<<t)+1][t];
}

int main()
{
    read(n,k,l,r);
    for(int i=1;i<=n;i++)
    {
        int x;
        read(x);
        sum[i]=sum[i-1]+x;
    }
    Log[0]=-1;
    for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1;
    build();
    for(int i=1;i<=n-l+1;i++)
    {
        int L=i+l-1,R=min(i+r-1,n);
        q.push((Node){i,L,R,query(L,R)});
    }
    ll ans=0;
    for(int i=1;i<=k;i++)
    {
        Node now=q.top();
        q.pop();
        ans+=sum[now.x]-sum[now.p-1];
        if(now.x>now.l)q.push((Node){now.p,now.l,now.x-1,query(now.l,now.x-1)});
        if(now.x<now.r)q.push((Node){now.p,now.x+1,now.r,query(now.x+1,now.r)});
    }
    printf("%lld\n",ans);
    return 0;
}