首页 > 代码库 > bzoj3524[Poi2014]Couriers*
bzoj3524[Poi2014]Couriers*
bzoj3524[Poi2014]Couriers
题意：
给一个长度为n的序列a。1≤a[i]≤n。m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。n，m≤500000。
题解：
先建主席树，之后在查找时，只走size值大于(r-l+1)/2的节点，如果两个儿子的size值都≤(r-l+1)/2则返回0否则返回最后走到的叶子节点。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 500010 6 using namespace std; 7 8 inline int read(){ 9 char ch=getchar(); int f=1,x=0;10 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}11 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();12 return f*x;13 }14 int tot,sz[maxn*23],ch[maxn*23][2],rt[maxn],n,a[maxn],m;15 void build(int &x,int l,int r){16 x=++tot; sz[x]=0; if(l==r)return; int mid=(l+r)>>1; build(ch[x][0],l,mid); build(ch[x][1],mid+1,r);17 }18 void insert(int &x,int l,int r,int v){19 tot++; sz[tot]=sz[x]+1; ch[tot][0]=ch[x][0]; ch[tot][1]=ch[x][1]; x=tot; if(l==r)return;20 int mid=(l+r)>>1; if(v<=mid)insert(ch[x][0],l,mid,v); if(v>mid)insert(ch[x][1],mid+1,r,v);21 sz[x]=sz[ch[x][0]]+sz[ch[x][1]];22 }23 int query(int ql,int qr){24 int x=(qr-ql+1)>>1,l=1,r=n,y=rt[qr],z=rt[ql-1];25 while(1){26 int mid=(l+r)>>1;27 if(sz[ch[y][0]]-sz[ch[z][0]]>x)y=ch[y][0],z=ch[z][0],r=mid;28 else if(sz[ch[y][1]]-sz[ch[z][1]]>x)y=ch[y][1],z=ch[z][1],l=mid+1;29 else if(l==r)return l; else return 0;30 }31 }32 int main(){33 n=read(); m=read(); build(rt[0],1,n); inc(i,1,n)rt[i]=rt[i-1],insert(rt[i],1,n,read());34 inc(i,1,m){35 int l=read(),r=read(); printf("%d\n",query(l,r));36 }37 return 0;38 }
20160908
bzoj3524[Poi2014]Couriers*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。