BZOJ_3524_[Poi2014]Couriers_主席树

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

分析：

区间众数我们可以用主席树搞定

具体地，比较左右子树siz大小即可

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 500050

int t[N*20],ls[N*20],rs[N*20],n,m;

int root[N],a[N],tot;

struct A{

	int num,id,v;

}d[N];

bool cmp1(const A &x,const A &y){ return x.num<y.num; }

bool cmp2(const A &x,const A &y){ return x.id<y.id; }

void insert(int x,int &y,int l,int r,int val){

	y=++tot;

	if(l==r) { t[y] = t[x] + 1; return ; }

	int mid=l+r>>1;

	if(val<=mid) rs[y]=rs[x],insert(ls[x],ls[y],l,mid,val);

	else ls[y]=ls[x],insert(rs[x],rs[y],mid+1,r,val);

	t[y]=t[ls[y]]+t[rs[y]];

}

int query(int x,int y,int l,int r,int len){

	if(l==r) return a[l];

	int mid=l+r>>1,sizls=t[ls[y]]-t[ls[x]],sizrs=t[rs[y]]-t[rs[x]];

	if(sizls>len/2) return query(ls[x],ls[y],l,mid,len);

	if(sizrs>len/2) return query(rs[x],rs[y],mid+1,r,len);

	return 0;

}

int main()

{

	scanf("%d%d",&n,&m);

	int i,x,y,j;

	for(i=1;i<=n;i++) scanf("%d",&d[i].num),d[i].id=i;

	sort(d+1,d+n+1,cmp1);d[0].num=20003535;

	for(i=1,j=0;i<=n;i++) { if(d[i].num!=d[i-1].num)j++;d[i].v=j;a[j]=d[i].num; }

	sort(d+1,d+n+1,cmp2);

	for(i=1;i<=n;i++) insert(root[i-1],root[i],1,n,d[i].v);

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

		scanf("%d%d",&x,&y);

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

	}

}

秒客网

BZOJ_3524_[Poi2014]Couriers_主席树

相关文章