题意：给出n个数和Q个询问（l,r)，对于每个询问求出(l,r)之间连续出现次数最多的次数。
代码：
/* rmq算法 当询问到x,y时，设在x之后并且与a[x]相同的最后一个数编号为t，那么x到t之间的数一定相同，t-x+1可能是答案；t+1到y之间的最大连续个数也可能是答案。那么我们设两个数组，hou[i]表示i之后并且与a[i]相同的最后一个数编号，num[i]表示到i为止a[i]连续出现的次数。当询问时，我们只需对两种答案取最大值即可。 */ #include<cstdio> #include<iostream> #include<cmath> #define M 100010 using namespace std; int a[M],num[M],hou[M],s[M][20],n,m; int main() { while(scanf("%d%d",&n,&m)==2) { if(!n)break; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(a[i]==a[i-1])num[i]=num[i-1]+1; else num[i]=1; s[i][0]=num[i]; } hou[n]=n; for(int i=n-1;i>=1;i--) if(a[i]==a[i+1])hou[i]=hou[i+1]; else hou[i]=i; for(int j=1;j<=18;j++) for(int i=1;i<=n;i++) { s[i][j]=s[i][j-1]; if(i+(1<<(j-1))<=n) s[i][j]=max(s[i][j],s[i+(1<<(j-1))][j-1]); } for(int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); int t=hou[a]; if(t>=b)printf("%d ",b-a+1); else { int ans1=t-a+1; a=t+1; int k=log(b-a+1)/log(2); int ans2=max(s[a][k],s[b-(1<<k)+1][k]); printf("%d ",max(ans1,ans2)); } } } return 0; }