Description
给一个长度为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
Sample Output
1 0 3 0 4
HINT
【数据范围】 n,m≤500000
2016.7.9重设空间，但未重测！
Source
思路
主席树+权值线段树
两颗树确定区间，然后树上跑二分。
代码实现
1 #include2 const int maxn=5e5+10; 3 int n,m,s[maxn]; 4 int hd[maxn]; 5 int ps,t[maxn<<5],ls[maxn<<5],rs[maxn<<5]; 6 int a,b,c; 7 void add(int pre,int suc,int l,int r,int v){ 8 t[suc]=t[pre]+1; 9 if(l==r) return;10 ls[suc]=ls[pre],rs[suc]=rs[pre];11 int mid=l+r>>1;12 if(v<=mid) ls[suc]=++ps,add(ls[pre],ls[suc],l,mid,v);13 else rs[suc]=++ps,add(rs[pre],rs[suc],mid+1,r,v);14 }15 int search(int pre,int suc,int l,int r,int v){16 while(l!=r){17 int mid=l+r>>1;18 if(t[ls[suc]]-t[ls[pre]]>v) suc=ls[suc],pre=ls[pre],r=mid;19 else if(t[rs[suc]]-t[rs[pre]]>v) suc=rs[suc],pre=rs[pre],l=mid+1;20 else return 0;21 }22 return l;23 }24 int main(){25 scanf("%d%d",&n,&m);26 for(int i=1;i<=n;i++){27 scanf("%d",&a);28 hd[i]=++ps;29 add(hd[i-1],hd[i],1,n,a);30 }31 for(int i=1;i<=m;i++){32 scanf("%d%d",&b,&c);33 printf("%d\n",search(hd[b-1],hd[c],1,n,c-b+1>>1));34 }35 return 0;36 }