H - Frequent values

Crawling in process...

Crawling failed

Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

Appoint description: bjtu_lyc (2011-08-08) System Crawler (2013-08-20)

Description

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.

Input

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.

Output

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

Sample Input

10 3-1 -1 1 1 1 1 3 10 10 102 31 105 100

Sample Output

143

思路：计算区间的相同个数，然后定个左右边界点，外加一个简单的RMQ。

#include
       
        #include
        
         #include
         
          #define FOR(i,a,b) for(int i=a;i<=b;++i)#define clr(f,z) memset(f,z,sizeof(f))#define ll(x) (1<
          
           r)return 0;  int t=bit[r-l+1];  r-=ll(t)-1;  return max(rmq[l][t],rmq[r][t]);}int main(){ int a,b;  while(scanf("%d",&N)&&N)  { scanf("%d",&Q);    f[0]=mm;f[N+1]=mm;    FOR(i,1,N)    {      scanf("%d",&f[i]);    }    int z=0,zs=f[1],kai=1;    FOR(i,1,N+1)    {      if(f[i]!=zs)        {          for(int j=i-1;f[j]==zs;--j)            f[j]=z,L[j]=kai,R[j]=i-1;          kai=i;z=1;zs=f[i];        }       else ++z;    }    initRMQ();    while(Q--)    {     scanf("%d%d",&a,&b);     int ans;     if(R[a]>L[b])ans=b-a+1;     else     ans=max(R[a]-a+1,b-L[b]+1);     ans=max(ans,RMQ(R[a]+1,L[b]-1));     printf("%d\n",ans);    }  }}