题目描述

给一个长度为n的序列a。1≤a[i]≤n。

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

输入

第一行两个数n，m。

第二行n个数，a[i]。

接下来m行，每行两个数l,r，表示询问[l,r]这个区间。

输出

m行，每行对应一个答案。

样例输入

7 5

1 1 3 2 3 4 3

1 3

1 4

3 7

1 7

6 6

样例输出

1

0

3

0

4

---

题解

主席树

同bzoj2223，也不需要离散化。

bzoj2223题解：http://www.cnblogs.com/GXZlegend/p/6292609.html

#include 
     
      int si[10000010] , lp[10000010] , rp[10000010] , root[500010] , tot;void pushup(int x){    si[x] = si[lp[x]] + si[rp[x]];}void ins(int x , int &y , int l , int r , int p){    y = ++tot;    if(l == r)    {        si[y] = si[x] + 1;        return;    }    int mid = (l + r) >> 1;    if(p <= mid) rp[y] = rp[x] , ins(lp[x] , lp[y] , l , mid , p);    else lp[y] = lp[x] , ins(rp[x] , rp[y] , mid + 1 , r , p);    pushup(y);}int query(int x , int y , int l , int r , int p){    if(l == r) return l;    int mid = (l + r) >> 1;    if(si[lp[y]] - si[lp[x]] > p) return query(lp[x] , lp[y] , l , mid , p);    if(si[rp[y]] - si[rp[x]] > p) return query(rp[x] , rp[y] , mid + 1 , r , p);    return 0;}int main(){    int n , m , i , a , b;    scanf("%d%d" , &n , &m);    for(i = 1 ; i <= n ; i ++ )    {        scanf("%d" , &a);        ins(root[i - 1] , root[i] , 1 , n , a);    }    while(m -- )    {        scanf("%d%d" , &a , &b);        printf("%d\n" , query(root[a - 1] , root[b] , 1 , n , (b - a + 1) >> 1));    }    return 0;}