本以为很简单的一个题，没想到时间缩短这么困难，我暂时都还没看懂，存一下
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2176
也是书上的一道题
把整个数组进行游程编码，用value[],coun[]数组记录第i段的数值和出现次数，用num[p]、left[p]、right[p]记录位置p处所在段的编号和左右端点的位置，，，
所以最后只需对3个部分求最大值即可。
第一部分，左端，right[L]-L+1
第二部分，中间，RMQ(coun, num[L]+1, num[R]+1);
第三部分，右端，R-left[R]+1
另外要注意：如果L，R在同一段，则答案是R-L+1;
代码如下：
其中最主要的就是要将题目给的数据，处理成（a,b）这种格式，表示数字a连续出现b次，并且记录每个编号对应的段号。然后我们在处理过后的以段为表示单位的数据上进行RMQ查询了。 #include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 100100 int value[maxn],cnt[maxn]; int num[maxn],left1[maxn],right1[maxn]; int dp[maxn][30],a[maxn]; void RMQ_Init(int t) { int n=t; for(int i=0;i<n;i++) dp[i][0]=cnt[i]; for(int j=1;(1<<j)<=n;j++) for(int i=0;i+(1<<j)-1<n;i++) dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } int RMQ(int L,int R) { int k=0; while((1<<(k+1)) <=R-L+1) k++; return max(dp[L][k],dp[R-(1<<k)+1][k]); } int main() { int n,q; freopen("in.txt","r",stdin); while(scanf("%d",&n)&&n) { scanf("%d",&q); for(int i=0;i<n;i++) scanf("%d",&a[i]); left1[0]=0; int t=0,tmp=1; for(int i=1;i<n;i++) { if(a[i]!=a[i-1]) { right1[t]=i-1; value[t]=a[i-1]; cnt[t]=tmp; t++; num[i]=t; left1[t]=i; tmp=1; } else { tmp++; num[i]=t; } } right1[t]=n-1; value[t]=a[n-1]; num[n-1]=t; cnt[t]=tmp; RMQ_Init(t); while(q--) { int x,y; scanf("%d%d",&x,&y); x--; y--; int L=num[x],R=num[y]; if(L==R) { printf("%d\n",y-x+1); continue; } int max0=0; max0=max(right1[L]-x+1,y-left1[R]+1); if(R-1>=L+1) max0=max(max0,RMQ(L+1,R-1)); printf("%d\n",max0); } } return 0; }