影魔 bzoj-4826 Hnoi-2017

题目大意：给定一个$n$个数的序列$a$，求满足一下情况的点对个数：

注释：$1\le n,m\le 2\cdot 10^5$，$1\le p1,p2\le 1000$。

想法：

我们先用单调栈求出一个数左边第一个比它大的，和右边第一个比它大的。$l_i$和$r_i$就表示这两个值。

然后我们发现，$(l_i,r_i)$就是一个合法的第一个条件的点对。

接下来我们考虑如何统计第二个条件的点对。

第二个条件的话如果还想用刚才的值表示的话，我们发现就是在平面上枚举一个线段，然后把这个线段染色。

每次统计一个矩形中多少个点是染色的。

而这个过程我们可以用主席树+标记永久化来实现的。

Code：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 200010

#define lson l,mid,ls[x],ls[y]

#define rson mid+1,r,rs[x],rs[y]

using namespace std; typedef long long ll;

char *p1,*p2,buf[100000];

#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)

int rd() {int x=0; char c=nc(); while(c<48) c=nc(); while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x;}

struct Node

{

	int x,l,r; ll p;

	Node() {}

	Node(int x_,int l_,int r_,ll p_) {x=x_,l=l_,r=r_,p=p_;}

}v[N<<2];

int a[N],lp[N],rp[N],sta[N],top,cnt,root[N],ls[N<<6],rs[N<<6],tot;

ll sum[N<<6],add[N<<6];

inline bool cmp(const Node &a,const Node &b) {return a.x<b.x;}

inline void pushup(int x) {sum[x]=sum[ls[x]]+sum[rs[x]];}

void insert(int b,int e,ll a,int l,int r,int x,int &y)

{

	y=++tot,ls[y]=ls[x],rs[y]=rs[x],add[y]=add[x],sum[y]=sum[x]+a*(e-b+1);

	if(b==l&&r==e) {add[y]+=a; return;}

	int mid=(l+r)>>1;

	if(e<=mid) insert(b,e,a,lson);

	else if(b>mid) insert(b,e,a,rson);

	else insert(b,mid,a,lson),insert(mid+1,e,a,rson);

}

ll query(int b,int e,int l,int r,int x,int y)

{

	if(b<=l&&r<=e) return sum[y]-sum[x];

	int mid=(l+r)>>1; ll ans=(add[y]-add[x])*(e-b+1);

	if(e<=mid) return ans+query(b,e,lson);

	else if(b>mid) return ans+query(b,e,rson);

	else return ans+query(b,mid,lson)+query(mid+1,e,rson);

}

int main()

{

	int n,m,i,j,x,y;

	ll p1,p2;

	n=rd(),m=rd(); p1=rd(),p2=rd(); for(int i=1;i<=n;i++) a[i]=rd();

	a[0]=a[n+1]=1<<30,top=1;

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

	{

		while(a[sta[top]]<a[i]) top--;

		lp[i]=sta[top],sta[++top]=i;

	}

	top=1,sta[1]=n+1;

	for(i=n;i>=1;i--)

	{

		while(a[sta[top]]<a[i])top--;

		rp[i]=sta[top],sta[++top]=i;

	}

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

	{

		if(lp[i]!=0&&rp[i]!=n+1) v[++cnt]=Node(lp[i],rp[i],rp[i],p1);

		if(i<n) v[++cnt]=Node(i,i+1,i+1,p1);

		if(lp[i]!=0&&rp[i]-i>1) v[++cnt]=Node(lp[i],i+1,rp[i]-1,p2);

		if(rp[i]!=n+1&&i-lp[i]>1) v[++cnt]=Node(rp[i],lp[i]+1,i-1,p2);

	}

	sort(v+1,v+cnt+1,cmp);

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

	{

		root[i]=root[i-1];

		while(j<=cnt&&v[j].x==i)

			insert(v[j].l,v[j].r,v[j].p,1,n,root[i],root[i]),j++;

	}

	while(m--)

	{

		x=rd(),y=rd();

		printf("%lld\n",query(x,y,1,n,root[x-1],root[y]));

	}

	return 0;

}

小结：好题。

巴特西

[bzoj4826][Hnoi2017]影魔_单调栈_主席树

影魔 bzoj-4826 Hnoi-2017

最新文章

热门文章