[poj3368]Frequent values(rmq)

题意：给出n个数和Q个询问（l,r)，对于每个询问求出(l,r)之间连续出现次数最多的次数。

解题关键：统计次数，转化为RMQ问题，运用st表求解，注意边界。

预处理复杂度：$O(n\log n)$

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cstdlib>

 #include<cmath>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 int a[],b[];

 int min1[][],max1[][],n,q;

 void rmq(int n){

     int lg=int(log10(n)/log10());

     for(int i=;i<=n;i++) min1[i][]=max1[i][]=b[i];

     for(int j=;j<=lg;j++){

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

             max1[i][j]=max(max1[i][j-],max1[i+(<<(j-))][j-]);

             //min1[i][j]=min(min1[i][j-1],min1[i+(1<<(j-1))][j-1]);

         }

     }

 }

 int query(int l,int r){

     if(l>r) return ;

     int k=(int)(log(r-l+)/log(2.0));

     return max(max1[l][k],max1[r-(<<k)+][k]);

 }

 int main(){

     int n,q;

     while(scanf("%d",&n)!=EOF&&n){

         scanf("%d",&q);

         for(int i=;i<=n;i++) scanf("%d",a+i);

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

             if(a[i]==a[i-]) b[i]=b[i-]+;

             else b[i]=;

         }

         rmq(n);

         while(q--){

             int t1,t2,t=;

             scanf("%d%d",&t1,&t2);

             t=t1;

                while(t<=t2&&a[t]==a[t-]) t++;

                 int maxres=query(t,t2);

                 maxres=max(maxres,t-t1);

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

             }

     }

     return ;

 }