bzoj 4826: [Hnoi2017]影魔【单调栈+树状数组+扫描线】

参考：https://www.cnblogs.com/lcf-2000/p/6789680.html

这是一个相对码量少的做法，用到了区间修改区间查询的树状数组，详见：www.cnblogs.com/lcf-2000/p/5866170.html#3830447

枚举最大值a[i]，找到l[i],r[i]是左边最后一个比它大的和右边第一个比它大的，考虑贡献：

p1：每次询问要先加上(r-l)*p1是点对相邻，然后对r[i]有p1贡献的左端点是l[i]

p2：对l[i]有贡献的是(i+1,r[i]-1)，对r[i]有贡献的是(l[i]+1,i-1)

离线排序+扫描线做就行，情况都要考虑到。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=400005;

int n,m,p1,p2,a[N],s[N],top,r[N],l[N],tot;

long long ans[N],c1[N],c2[N];

struct qwe

{

	int l,r,x,b,z;

	qwe(int L=0,int R=0,int X=0,int B=0,int Z=0)

	{

		l=L,r=R,x=X,b=B,z=Z;

	}

}b[N],c[N];

bool cmp(const qwe &a,const qwe &b)

{

	return a.x<b.x;

}

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;

}

int lb(int x)

{

	return x&(-x);

}

void add(int x,int v)

{

	if(!x)

		return;

	for(int i=x;i<=n;i+=lb(i))

		c1[i]+=v,c2[i]+=1ll*x*v;

}

long long ques(int x)

{

	long long re=0;

	for(int i=x;i>0;i-=lb(i))

		re+=(x+1)*c1[i]-c2[i];

	return re;

}

int main()

{

	n=read(),m=read(),p1=read(),p2=read();

	a[0]=a[n+1]=n+1;

	s[top=1]=0;

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

	{

		if(i<=n)

			a[i]=read();

		while(a[s[top]]<a[i])

			r[s[top--]]=i;

		l[i]=s[top];

		s[++top]=i;

	}

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

	{

		int l=read(),r=read();

		ans[i]+=(r-l)*p1;//相邻两个点产生的贡献

		b[i]=qwe(l,r,l-1,i,-1);

		b[i+m]=qwe(l,r,r,i,1);

	}

	sort(b+1,b+1+2*m,cmp);

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

	{

		if(l[i]&&r[i]<=n)

			c[++tot]=qwe(l[i],l[i],r[i],0,p1);

		if(l[i]&&r[i]>i+1)

			c[++tot]=qwe(i+1,r[i]-1,l[i],0,p2);

		if(r[i]<=n&&i>l[i]+1)

			c[++tot]=qwe(l[i]+1,i-1,r[i],0,p2);

	}

	sort(c+1,c+1+tot,cmp);

	int w1=1,w2=1;

	while(!b[w1].x)

		w1++;

	for(int i=1;w1<=m*2&&i<=n;i++)//扫描线

	{

		while(w2<=tot&&c[w2].x==i)

		{

			add(c[w2].r+1,-c[w2].z);

			add(c[w2].l,c[w2].z);

			w2++;

		}

		while(w1<=2*m&&b[w1].x==i)

		{

			ans[b[w1].b]+=b[w1].z*(ques(b[w1].r)-ques(b[w1].l-1));

			w1++;

		}

	}

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

		printf("%lld\n",ans[i]);

	return 0;

}

巴特西

bzoj 4826: [Hnoi2017]影魔【单调栈+树状数组+扫描线】

最新文章

热门文章