[洛谷 2048][NOI2010]超级钢琴

题目链接

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据