题目：[NOI2010] 超级钢琴

前求出美妙值的前缀和，然后倍增处理一下前缀和的最大值，然后对于一个左端点s，他能取到右端点的只有s+l到s+r，而他的最大贡献就是s+l 到s+r的最大子段和，因此可以直接维护，然后用个堆维护总和最大值，这道题就做完了。

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

#define int long long

const int N=5e5+5;

using namespace std;

int n,m,L,R,f[N][20],a[N],sum[N],lg[N];

namespace ST

{

	void init()

	{

		for(int j=1;(1<<j)<=n;j++)

		    for(int i=1;i+(1<<j)-1<=n;i++)

		    {

		    	int s1=f[i][j-1],s2=f[i+(1<<(j-1))][j-1];

		        if(sum[s1]>=sum[s2])

		            f[i][j]=s1;

		        else

				    f[i][j]=s2;

			}

	}

	int query(int l,int r)

	{

		int j=lg[r-l+1];

		int s1=f[l][j],s2=f[r-(1<<j)+1][j];

		if(sum[s1]>=sum[s2])

		    return s1;

		else

		    return s2;

	}

}

using namespace ST;

struct pos

{

	int o,l,r,val,maxp;

	pos(int oo,int ll,int rr)

	{

		o=oo;l=ll;r=rr;

		maxp=query(l,r);

		val=sum[maxp]-sum[o-1];

	}

	pos(){

	}

	friend bool operator < (pos a,pos b)

	{

		return a.val<b.val;

	}

};

priority_queue <pos> q;

signed main()

{

	scanf("%lld %lld %lld %lld",&n,&m,&L,&R);

	for(int i=1;i<=n;i++)

	{

	    scanf("%lld",&a[i]);

		f[i][0]=i;

		sum[i]=sum[i-1]+a[i];

	}

	for(int i=2;i<=n;i++)

	    lg[i]=lg[i>>1]+1;

	init();

	for(int i=1;i<=n;i++)

	    if(i+L-1<=n)

	        q.push(pos(i,i+L-1,min(i+R-1,n)));

	int ret=0;

	for(int i=1;i<=m;i++)

	{

		pos now=q.top();

		q.pop();

		ret+=now.val;

		if(now.maxp-1>=now.l)

		    q.push(pos(now.o,now.l,now.maxp-1));

		if(now.maxp+1<=now.r)

		    q.push(pos(now.o,now.maxp+1,now.r));

	}

	printf("%lld\n",ret);

	return 0;

}

巴特西

2022春每日一题：Day 40

题目：[NOI2010] 超级钢琴

最新文章

热门文章