#include<iostream>
#include<cmath>
using namespace std;
//rmq
//题意：给定一个非递减的序列，a1,a2,a3....an，给出一系列询问RMQ[i,j],问在区间[i,j]上出现频率最高的数字
//这个最高相当于RMQ中的最大，那么问题的关键就成了如何将他转化成可解的RMQ模型
//这里有个很关键的信息，就是非递减，那么数字都是连续出现，出了这段，在其他地方便不可能出现了
//那么我们可以预处理下每个数字的左右边界以及频数，那么在区间查询时根据这个可以计算出当前区间内，某个数的频数，想想是不是如此
//这样离散化操作后给定一个区间，那么区间中有哪些数，数的频率都确定下来了
//考率中间的连续段，做RMQ，然后取最大和左右剩余的区间比较，若就在某个区间内部单独考虑 
int n,q,len;//len代表区间段的个数 
int a[100005]; 
int l[100005],r[100005],h[100005];//l，r，h，记录离散后的区间段起始，结束，频数 注意下标表示的是区间段 
int ll[100005],rr[100005];//记录具体每个数的起始，结束 具体到原数列每一项 
int dp[20][100005];
int d[100005]; 
int MAX(int x,int y)
{
    return x>y?x:y;
    }
void RMQ()//只对连续的完整的段进行处理，这里吧段看成是一个元素
{
    int i,j;
    for(i=1;i<=len;i++)dp[0][i]=h[i];
    for(j=1;j<=int(log((double)n)/log(2.0));j++) 
    {
        for(i=1;i+(1<<j)-1<=len;i++)
        {
            dp[j][i]=MAX(dp[j-1][i],dp[j-1][i+(1<<(j-1))]);                      
            }                                        
        } 
    }        
int query(int i,int j)//参数表示左右两段的区间编号
{
    int k=int(log((double)(j-i+1))/log(2.0));//获得步长 
    return MAX(dp[k][i],dp[k][j-(1<<k)+1]);
    }            
int main()
{
    int i,j,k,c,x,y,t,left,right,xx,yy,max;
    while(scanf("%d",&n)!=EOF)
    {
          if(n==0)break;                    
          scanf("%d",&q);
          for(i=1;i<=n;i++)
          {
              scanf("%d",&a[i]);             
              }                 
          a[n+1]=200000;
          len=1;
          for(i=1;i<=n;i++)
          {
              l[len]=i;
              c=0;
              while(a[i]==a[i+1]){i++;c++;}
              r[len]=l[len]+c;
              h[len]=c+1;
              len++;                           
              }
          len--;
/*          for(i=1;i<=len;i++)
          {
              cout<<"left="<<l[i]<<endl;
              cout<<"right="<<r[i]<<endl;               
              }*/
          for(i=1;i<=len;i++)
          {
              for(j=l[i];j<=r[i];j++)//把区间段的数处理好 
              {
                  a[j]=h[i];//把每个位置修改成了频数样例编程了2，2，4，4，4，4，1，3，3，3 
                  ll[j]=l[i];//1，1，3，3，3，3，7，8，8，8 
                  rr[j]=r[i];//2，2，6，6，6，6，7，10，10，10
                  d[j]=i;//  1，1，2，2，2，2，3，4，4，4 编号                   
                  }               
              }
//          for(i=1;i<=n;i++)测试数据    
          RMQ();    
          for(i=1;i<=q;i++)
          {
              scanf("%d%d",&x,&y);
//              cout<<query(x,y)<<endl;
              if(x>y){t=x;x=y;y=t;}
              if(ll[x]==ll[y])//表示在同一段
              {
                 printf("%d\n",y-x+1);
                 continue;                           
                 }        
              xx=0;
              yy=0;
//              cout<<"x="<<x<<" y="<<y<<endl;
              if(ll[x]<x){xx=rr[x]-x+1;x=rr[x]+1;}//获取左段，更新边界 
              if(rr[x]>y){yy=y-ll[y]+1;y=ll[x]-1;}//获取右段，更新边界
              max=0;
//              cout<<"x="<<x<<" y="<<y<<endl; 
              if(x<y)max=query(d[x],d[y]);
//              cout<<d[x]<<" "<<d[y]<<endl;
//              cout<<"max="<<max<<endl;
              max=MAX(max,xx);
              max=MAX(max,yy);
              printf("%d\n",max);        
              }                       
          }
    return 0;
    }

• Re:哪位给点测试数据 (13) foreverlin 2009-05-07 14:28:48