[BZOJ3524]区间问题（主席树）

Description

给一个长度为n的序列a。1≤a[i]≤n。m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。

Solution

用主席树处理即可，

由于按值建树，其实只要不断判断左右子树子节点数量大于（r-l+1）/2就行了

Code

#include <cstdio>

#include <algorithm>

#define N 500010

using namespace std;

int n,m,A[N],rank[N],T[N],ls[N*20],rs[N*20],sum[N*20],tot;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

void update(int last,int p,int l,int r,int &rt){

	rt=++tot;

	ls[rt]=ls[last],rs[rt]=rs[last],sum[rt]=sum[last]+1;

	if(l==r) return;

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

	if(p<=m) update(ls[last],p,l,m,ls[rt]);

	else update(rs[last],p,m+1,r,rs[rt]);

}

int Query(int ss,int tt,int l,int r,int k){

	if(l==r) return l;

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

	if(k<sum[ls[tt]]-sum[ls[ss]]) return Query(ls[ss],ls[tt],l,m,k);

	else if(k<sum[rs[tt]]-sum[rs[ss]]) return Query(rs[ss],rs[tt],m+1,r,k);

	else return 0;

}

int main(){

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

	for(int i=1;i<=n;++i) A[i]=rank[i]=read();

	sort(rank+1,rank+n+1);

	int cnt=unique(rank+1,rank+n+1)-(rank+1);

	for(int i=1;i<=n;++i) A[i]=lower_bound(rank+1,rank+cnt+1,A[i])-rank;

	for(int i=1;i<=n;++i) update(T[i-1],A[i],1,cnt,T[i]);

	while(m--){

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

		printf("%d\n",rank[Query(T[l-1],T[r],1,cnt,(r-l+1)>>1)]);

	}

	return 0;

}

巴特西

[BZOJ3524]区间问题（主席树）

Description

Solution

Code

最新文章

热门文章