目录
显示
题目链接
https://www.luogu.com.cn/problem/P2048
题解
显然，要将所有满足条件的区间和全部求出来是不现实的。
注意到区间和有一个优美的性质：设前缀和为 \(s_i\)，则：
$$\sum_{i=l}^r a_i = s_r – s_{l-1}$$
一旦左端点固定，我们只需找到最大的 \(s_r\)，即可求出以 \(l\) 为左端点的最大区间和。
而区间 \(s_i\) 的最大值可以用 ST 表方便地维护。
我们设 \(f(l,r_1,r_2)\) 表示以 \(l\) 为区间左端点，区间右端点的范围在 \([r_1,r_2]\) 之间时的最大区间和。
刚开始枚举所有可行的 \(l\)，用 ST 表算出 \([r_1,r_2]\) 的最大 \(s_i\)，将所有的 \(f(l,r_1,r_2)\) 放入一个大根堆中。
接下来每次从大根堆中取出一个区间和，累加到答案中。
把 \(f(l,r_1,r_2)\) 这个状态取出来后，设它的最大区间和在 \(t\) 处取到，则我们需要将这个状态拆分成两个新的状态 \(f(l,r_1,t-1)\) 和 \(f(l,t+1,r_2)\)（记得判断右端点的范围是否非空），重新插入到堆中。
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n,k,l,r;
int f[500005][25],a[500005];
struct node
{
int l,r1,r2,pos,res;
bool operator<(const node&a)const
{
return res<a.res;
}
};
priority_queue<node> q;
void init()
{
for(int i=1;i<=n;i++)
f[i][0]=i;
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<(j-1))-1<=n;i++)
{
int x=f[i][j-1],y=f[i+(1<<(j-1))][j-1];
if(a[x]>a[y])f[i][j]=x;
else f[i][j]=y;
}
}
int query(int l,int r)
{
int len=r-l+1;
int k=log2(len);
int x=f[l][k],y=f[r-(1<<k)+1][k];
if(a[x]>a[y])return x;
return y;
}
int main()
{
cin>>n>>k>>l>>r;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]+=a[i-1];
}
init();
for(int i=1;i<=n-l+1;i++)
{
int lpos=i+l-1,rpos=min(n,i+r-1),pos=query(lpos,rpos);
int res=a[pos]-a[i-1];
q.push({i,lpos,rpos,pos,res});
}
long long ans=0;
while(k--)
{
int l=q.top().l,r1=q.top().r1,r2=q.top().r2,pos=q.top().pos,res=q.top().res;
q.pop();
ans+=res;
if(pos-1>=r1)
{
int np=query(r1,pos-1);
int res=a[np]-a[l-1];
q.push({l,r1,pos-1,np,res});
}
if(pos+1<=r2)
{
int np=query(pos+1,r2);
int res=a[np]-a[l-1];
q.push({l,pos+1,r2,np,res});
}
}
cout<<ans<<endl;
return 0;
}