首页 > 代码库 > 【BZOJ3956】Count 主席树+单调栈

【BZOJ3956】Count 主席树+单调栈

2024-10-18 19:17:38   210人阅读

【BZOJ3956】Count

Description

技术分享

Input

技术分享

Output

技术分享

Sample Input

3 2 0
2 1 2
1 1
1 3

Sample Output

0
3

HINT

M,N<=3*10^5,Ai<=10^9

题解：影魔那道题的简化版，依旧用单调栈记录每个数左（右）边第一个比它大的数为ld[i],rd[i]，那么合法的点对只有（i,i+1）和（ld[i],rd[i]）两种。为了防止重复，我们记录每个数左边第一个>=它的数le[i]，当且仅当le[i]==ld[i]的时候我们才统计这样的点对。然后就变成了在一个二维平面内有一些点，每次问你一个矩形中点的个数，用主席树就行了。

但是自从观摩了单调栈+ST表的做法后感觉自己的做法烂成渣~

#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int maxn=300010;int n,m,typ,ans,tot,top,cnt;struct sag{	int ls,rs,sum;}s[maxn*30];int ld[maxn],rd[maxn],le[maxn],v[maxn],st[maxn],to[maxn],next[maxn],head[maxn],rt[maxn];void add(int a,int b){	to[++cnt]=b,next[cnt]=head[a],head[a]=cnt;}int readin(){	int ret=0;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	gc=getchar();	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret;}void insert(int x,int &y,int l,int r,int pos){	if(!y||y==x)	y=++tot,s[y].sum=s[x].sum;	s[y].sum++;	if(l==r)	return ;	int mid=l+r>>1;	if(pos<=mid)	s[y].rs=(!s[y].rs)?s[x].rs:s[y].rs,insert(s[x].ls,s[y].ls,l,mid,pos);	else	s[y].ls=(!s[y].ls)?s[x].ls:s[y].ls,insert(s[x].rs,s[y].rs,mid+1,r,pos);}int query(int x,int y,int l,int r,int a,int b){	if(a<=l&&r<=b)	return s[y].sum-s[x].sum;	int mid=l+r>>1;	if(b<=mid)	return query(s[x].ls,s[y].ls,l,mid,a,b);	if(a>mid)	return query(s[x].rs,s[y].rs,mid+1,r,a,b);	return query(s[x].ls,s[y].ls,l,mid,a,b)+query(s[x].rs,s[y].rs,mid+1,r,a,b);}int main(){	int i,j,a,b;	n=readin(),m=readin(),typ=readin();	for(i=1;i<=n;i++)	v[i]=readin();	for(top=0,i=1;i<=n;i++)	{		while(top&&v[st[top]]<v[i])	rd[st[top--]]=i;		if(top)	le[i]=st[top];		st[++top]=i;	}	while(top)	rd[st[top--]]=n+1;	for(top=0,i=1;i<=n;i++)	{		while(top&&v[st[top]]<=v[i])	top--;		if(top)	ld[i]=st[top];		st[++top]=i;		if(ld[i]&&ld[i]==le[i])	add(rd[i],ld[i]);	}	for(i=1;i<=n;i++)	{		if(i>1)	insert(rt[i-1],rt[i],1,n,i-1);		for(j=head[i];j;j=next[j])	insert(rt[i-1],rt[i],1,n,to[j]);	}	for(i=1;i<=m;i++)	{		a=(readin()+ans-1)%n+1,b=(readin()+ans-1)%n+1;		if(a>b)	swap(a,b);		printf("%d\n",ans=query(rt[a-1],rt[b],1,n,a,b)),ans*=typ;	}	return 0;}

【BZOJ3956】Count 主席树+单调栈


联系
我们