Luogu P2048 【NOI2010】超级钢琴|堆+ST表

题目链接
题意：

有一架超级钢琴，可弹 (n) 个音符，第 (i) 个音符权值 (a_i)。定义超级和弦为一段长度不小于 (L) 且不大于 (R) 的子序列，求前 (k) 大的超级和弦的权值之和。
(n le 5 imes 10^5) , (k le 5 imes 10^5) , (-1000le a_i le 1000)
题解：

之前GDKOI2021提到过，可能是一个比较常见的trick？
简而言之，这个trick是针对类似本题的“可伸缩区间问题”，对于每个点 (i) ,取以此为起点，长度为 (L) 到 (R) 的序列中和最大的一段（记该结果为 ((x,L,R)) ，该结果需要记录长度（设为 (t_i)），权值，以及 (x) 本身等数据。需要注意的是，这里的 (L) 和 (R) 随着找下一最大值的过程会发生改变，故需维护）。将所有的 ((x,L,R)) 按权值由大到小的顺序放入堆中。取出一个 ((x,L,R)) 后，则加入 ((x,L,t_i-1)) 以及 ((x,t_i+1,R))。不难看出，这样取可以取出以 (i) 为起点的第二，第三大序列。以此类推。

对于本题，剩下的就是维护最大段了。这显然不能暴力，注意到该序列为无修改的，故选择前缀和快速求和，通过码量较小的ST表维护 ((x,L,R)) 即可解决最大段的维护。具体来讲，ST表维护的是由 (1) 到 (L)的前缀和和由 (1) 到 (R) 之间的前缀和的最大值，查询时减去由 (1) 到 (x-1) 的前缀和即可。

上代码：

#include<bits/stdc++.h>
#define N 500500
using namespace std;
struct data
{
	int x,xx,num,L,R;
}h[N*3];
int n,k,l,r,a[N],f[N][22],fa[N][22];
long long g,ans;
bool cmp(data x,data y)
{
	return x.x<y.x;
}
int fin(int x,int L,int R)
{
	if (x+R-1>n) R=n-x+1;
	if (L>R) return 0;
	int c=0;
	for (int i=1;i<=19;i++)
	  if ((1<<i)>=R-L+1) {c=i-1;break;}
	if (f[x+L-1][c]>=f[x+R-(1<<c)][c]) return fa[x+L-1][c]-x+1;
	else return fa[x+R-(1<<c)][c]-x+1;
}
void add(int num,int x,int xx,int l,int r)
{
	g++;int fa=g/2,so=g;
	h[g].x=x;h[g].xx=xx;h[g].num=num;h[g].L=l;h[g].R=r;
	while (cmp(h[fa],h[so])&&fa)
	{
		swap(h[fa],h[so]);
		so=fa;fa=fa/2;
	}
}
data del()
{
	data tmd=h[1];
	h[1]=h[g];g--;
	int fa=1,so=2;
	if (cmp(h[so],h[so+1])&&so+1<=g) so++;
	while (cmp(h[fa],h[so])&&so<=g)
	{
		swap(h[fa],h[so]);
		fa=so;so*=2;
		if (cmp(h[so],h[so+1])&&so+1<=g) so++;
	}
	return tmd;
}
int main()
{
	cin>>n>>k>>l>>r;
	for (int i=1;i<=n;i++)
	{
		cin>>a[i];
		f[i][0]=f[i-1][0]+a[i];fa[i][0]=i;
	} 
	for (int i=1;i<=19;i++)
	{
		for (int j=1;j<=n-(1<<i)+1;j++)
		{
		  if (f[j][i-1]>=f[j+(1<<(i-1))][i-1])	
		  f[j][i]=f[j][i-1],fa[j][i]=fa[j][i-1];
		  else f[j][i]=f[j+(1<<(i-1))][i-1],fa[j][i]=fa[j+(1<<(i-1))][i-1];
		}
	}//ST表维护$(x,L,R)$
	for (int i=1;i<=n-l+1;i++)
	{
		int tmp=fin(i,l,r);
		add(i,f[i+tmp-1][0]-f[i-1][0],tmp,l,r); 
	}//初始化堆
	for (int i=1;i<=k;i++)
	{
		data tmd=del();
		ans+=tmd.x;
		int tmp=fin(tmd.num,tmd.L,tmd.xx-1);
		if (tmp) add(tmd.num,f[tmd.num+tmp-1][0]-f[tmd.num-1][0],tmp,tmd.L,tmd.xx-1);
		tmp=fin(tmd.num,tmd.xx+1,tmd.R);
		if (tmp) add(tmd.num,f[tmd.num+tmp-1][0]-f[tmd.num-1][0],tmp,tmd.xx+1,tmd.R);
	}//维护存放$(x,L,R)$的堆	
	cout<<ans<<endl;
	return 0;
}

Luogu P2048 【NOI2010】 超级钢琴|堆+ST表

相关推荐

Luogu P2048 【NOI2010】超级钢琴|堆+ST表