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

Solution

就是递归查询区间sum是否大于(r-l+1)/2，是的话就递归左右儿子，否则return

如果能一直递归到l==r就是有解，否则无解

Code

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define N (300000+100) 6 using namespace std; 7 struct node{
   int lson,rson,sum;}Segt[N*40]; 8 int a[N],b[N],n,m,Root[N],Segt_cnt,x,y,lim; 9 10 int Build(int l,int r)11 {12     int node=++Segt_cnt;13     if (l==r) return node;14     int mid=(l+r)>>1;15     Segt[node].lson=Build(l,mid);16     Segt[node].rson=Build(mid+1,r);17     return node;18 }19 20 int Update(int pre,int l,int r,int x)21 {22     int node=++Segt_cnt;23     Segt[node].sum=Segt[pre].sum+1;24     Segt[node].lson=Segt[pre].lson;25     Segt[node].rson=Segt[pre].rson;26     if (l==r) return node;27     int mid=(l+r)>>1;28     if (x<=mid) Segt[node].lson=Update(Segt[node].lson,l,mid,x);29     else Segt[node].rson=Update(Segt[node].rson,mid+1,r,x);30     return node;31 }32 33 int Query(int u,int v,int l,int r)34 {35     int mid=(l+r)>>1,c=Segt[v].sum-Segt[u].sum;36     if (c<=(y-x+1)>>1) return 0;37     if (l==r) return b[l];    38     return max(Query(Segt[u].lson,Segt[v].lson,l,mid),Query(Segt[u].rson,Segt[v].rson,mid+1,r));39 }40 41 int main()42 {43     scanf("%d%d",&n,&lim);44     for (int i=1;i<=n;++i)45         scanf("%d",&a[i]),b[i]=a[i];46     sort(b+1,b+n+1);47     int num=unique(b+1,b+n+1)-b-1;48     Root[0]=Build(1,num);49     for (int i=1;i<=n;++i)50     {51         int t=lower_bound(b+1,b+num+1,a[i])-b;52         Root[i]=Update(Root[i-1],1,num,t);53     }54     scanf("%d",&m);55     for (int i=1;i<=m;++i)56     {57         scanf("%d%d",&x,&y);58         int ans=Query(Root[x-1],Root[y],1,num);59         if (ans) printf("yes %d\n",ans);60         else printf("no\n");61     }62 }