首页 > 代码库 > 3524: [Poi2014]Couriers -- 主席树
3524: [Poi2014]Couriers -- 主席树
3524: [Poi2014]Couriers
Time Limit: 20 Sec Memory Limit: 256 MBDescription
给一个长度为n的序列a。1≤a[i]≤n。
m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。
Input
第一行两个数n，m。
第二行n个数，a[i]。
接下来m行，每行两个数l,r，表示询问[l,r]这个区间。
Output
m行，每行对应一个答案。
Sample Input
7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
Sample Output
1
0
3
0
4
0
3
0
4
HINT
【数据范围】
n,m≤500000
#include<cstdio>#define N 10000010#define M 500010inline 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;}int n,m,sz,rt[M],ls[N],rs[N],sum[N];inline void add(int l,int r,int a,int &p,int v){ p=++sz;sum[p]=sum[a]+1; if(l==r)return; ls[p]=ls[a];rs[p]=rs[a]; int mid=(l+r)>>1; if(v<=mid) add(l,mid,ls[a],ls[p],v); else add(mid+1,r,rs[a],rs[p],v);}inline int qwq(int L,int R){ int x=rt[L-1],y=rt[R],md=(R-L+1)>>1,l=1,r=n,mid; while(l<r) { if(sum[y]-sum[x]<=md) return 0; mid=(l+r)>>1; if(sum[ls[y]]-sum[ls[x]]>md){r=mid;x=ls[x];y=ls[y];} else if(sum[rs[y]]-sum[rs[x]]>md){l=mid+1;x=rs[x];y=rs[y];} else return 0; } return l;}int x,l,r;int main(){ n=read();m=read(); for(int i=1;i<=n;i++) { x=read(); add(1,n,rt[i-1],rt[i],x); } while(m--) { l=read();r=read(); printf("%d\n",qwq(l,r)); }}
3524: [Poi2014]Couriers -- 主席树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。