目录
显示
题目链接
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; }