Frequent values

　　You are given a sequence of n integers a₁ , a₂ , ... , a_n in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers a_i , ... , a_j.

　　The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a₁ , ... , a_n (-100000 ≤ a_i ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: a_i ≤ a_i+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the
query.

The last test case is followed by a line containing a single 0.

　　For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int maxn=;

 int mm[maxn],Max[maxn][];

 int MAXL[maxn],MAXR[maxn],cnt=;

 int ID[maxn],tot[maxn],a[maxn];

 void Init(){

     memset(tot,,sizeof(tot));

     cnt=;

 }

 int main(){

 #ifndef ONLINE_JUDGE

     //freopen(".in","r",stdin);

     //freopen(".out","w",stdout);

 #endif

     int n,Q;

     while(~scanf("%d",&n)&&n){

         scanf("%d",&Q);

         Init();

         for(int i=;i<=n;i++)

             scanf("%d",&a[i]);

         a[]=a[n+]=-;

         for(int i=;i<=n;i++){

             if(a[i]==a[i-]){

                 MAXL[i]=MAXL[i-];

                 ID[i]=ID[i-];

             }

             else{

                 MAXL[i]=i;

                 ID[i]=++cnt;

             }

             tot[ID[i]]++;

         }

         //MAXL[i]指与a[i]相等的1~i-1中最靠左的位置

         //ID[i]指当前位置被分到第几块

         //tot[i]指第i块的长度

         for(int i=n;i>=;i--){

             if(a[i]==a[i+])

                 MAXR[i]=MAXR[i+];

             else

                 MAXR[i]=i;

         }

         //MAXR[i]指与a[i]相等的i+1~n中最靠右的位置

         mm[]=-;

         for(int i=;i<=cnt;i++){

             mm[i]=(i&(i-))?mm[i-]:mm[i-]+;

             Max[i][]=tot[i];

         }

         for(int k=;k<=mm[cnt];k++)

             for(int i=;i+(<<k)-<=cnt;i++)

                 Max[i][k]=max(Max[i][k-],Max[i+(<<(k-))][k-]);

         //对块处理出稀疏表

         int a,b,ans;

         while(Q--){

             scanf("%d%d",&a,&b);

             if(a>b)swap(a,b);

             if(ID[a]==ID[b]){

                 printf("%d\n",b-a+);

                 continue;

             }

             ans=-;

             ans=max(MAXR[a]-a+,b-MAXL[b]+);

             a=ID[MAXR[a]+];

             b=ID[MAXL[b]-];

             if(a<=b)

                 ans=max(ans,max(Max[a][mm[b-a+]],Max[b-(<<mm[b-a+])+][mm[b-a+]]));

             printf("%d\n",ans);

         }

     }

     return ;

 }