RMQ问题；
采用游程编码；
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define maxn 100009 5 using namespace std; 6 7 int d[maxn][30],value[maxn],cnt[maxn],num[maxn],left[maxn],right[maxn]; 8 9 void RMQ_init(int n) 10 { 11 for(int i=1; i<=n; i++)d[i][0]=cnt[i]; 12 for(int j=1; (1<<j)<=n; j++) 13 for(int i=1; i+(1<<j)-1<=n; i++) 14 d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]); 15 } 16 17 int RMQ(int l,int r) 18 { 19 if(l>r)return 0; 20 int k=0; 21 while(1<<(k+1)<=r-l+1)k++; 22 return max(d[l][k],d[r-(1<<k)+1][k]); 23 } 24 25 int main() 26 { 27 int n,m,q,x; 28 while(scanf("%d",&n)&&n) 29 { 30 scanf("%d",&q); 31 memset(right,0,sizeof right); 32 m=0; 33 for(int i=1;i<=n;i++) 34 { 35 scanf("%d", &x); 36 if(!m||value[m]!=x) 37 { 38 value[++m]=x; 39 cnt[m]=1; 40 } 41 else cnt[m]++; 42 num[i]=m; 43 } 44 cnt[m+1]=n; 45 int k=1,tmpleft=1,tmpright=cnt[1]; 46 for(int i=1;i<=m;i++) 47 { 48 for(int j=1;j<=cnt[i];j++) 49 { 50 left[k]=tmpleft; 51 right[k++]=tmpright; 52 } 53 tmpleft+=cnt[i]; 54 tmpright+=cnt[i+1]; 55 } 56 RMQ_init(m); 57 int l,r; 58 while(q--) 59 { 60 scanf("%d%d",&l,&r); 61 if(left[l]==left[r])printf("%d ",r-l+1); 62 else printf("%d ",max(max(right[l]-l+1,r-left[r]+1),RMQ(num[l]+1,num[r]-1))); 63 } 64 } 65 return 0; 66 }