bzoj 2006: [NOI2010]超级钢琴【st表+堆】

设计一个五元组(i,l,r,p,v)，表示在以i为左端点，右端点落在(l,r)中的情况下，取最大值v时右端点落在p。把这个五元组塞到优先队列里，以v排序，每次取出一个，然后把这个取过的五元组分成两个(i,l,p-1,p',v')(i,p+1,r,p'',v'')塞回去。

关于如何确定v和p，先求前缀和s，然后选择st表，注意这里的st表存的是位置，s[i][0]=i，然后取max的操作改成mx:return s[a]>s[b]?a:b;就可以了，不用存两个（我因为存了两个WAWAWA…然而至今不知道为啥

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

const int N=550005;

int n,m,l,r,a[N],st[N][20],b[N],s[N];

long long ans;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

struct qwe

{

	int i,l,r,v,p;

	bool operator < (const qwe &a) const

	{

		return v<a.v;

	}

};

priority_queue<qwe>q;

int mx(int a,int b)

{

	return s[a]>s[b]?a:b;

}

void add(int i,int l,int r)

{

	qwe now;

	now.i=i,now.l=l,now.r=min(r,n);

	if(now.l>now.r)

		return;

	int k=b[now.r-now.l+1];

	now.p=mx(st[now.l][k],st[now.r-(1<<k)+1][k]);

	now.v=s[now.p]-s[now.i-1];//cout<<now.i<<" "<<now.l<<" "<<now.r<<" "<<now.p<<" "<<now.v<<endl;

	q.push(now);

}

int main()

{

	n=read(),m=read(),l=read(),r=read();

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

	{

		a[i]=read();

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

		st[i][0]=i;

	}

	b[1]=0;

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

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

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

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

            st[i][j]=mx(st[i][j-1],st[i+(1<<j-1)][j-1]);

	for(int i=1;i<=min(n,n-l+1);i++)

		add(i,i+l-1,i+r-1);

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

	{

		qwe now=q.top();

		q.pop();//cout<<now.i<<" "<<now.l<<" "<<now.r<<" "<<now.p<<" "<<now.v<<endl;

		ans+=now.v;

		add(now.i,now.l,now.p-1);

		add(now.i,now.p+1,now.r);

	}

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

	return 0;

}

巴特西

bzoj 2006: [NOI2010]超级钢琴【st表+堆】

最新文章

热门文章