题意：给出n个数和Q个询问（l,r)，对于每个询问求出(l,r)之间连续出现次数最多的次数。
解题关键：统计次数，转化为RMQ问题，运用st表求解，注意边界。
预处理复杂度：$O(nlog n)$
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<cmath> 6 #include<iostream> 7 using namespace std; 8 typedef long long ll; 9 int a[100002],b[100002]; 10 int min1[100002][22],max1[100002][22],n,q; 11 void rmq(int n){ 12 int lg=int(log10(n)/log10(2)); 13 for(int i=1;i<=n;i++) min1[i][0]=max1[i][0]=b[i]; 14 for(int j=1;j<=lg;j++){ 15 for(int i=1;i+(1<<j)-1<=n;i++){ 16 max1[i][j]=max(max1[i][j-1],max1[i+(1<<(j-1))][j-1]); 17 //min1[i][j]=min(min1[i][j-1],min1[i+(1<<(j-1))][j-1]); 18 } 19 } 20 } 21 22 int query(int l,int r){ 23 if(l>r) return 0; 24 int k=(int)(log(r-l+1)/log(2.0)); 25 return max(max1[l][k],max1[r-(1<<k)+1][k]); 26 } 27 int main(){ 28 int n,q; 29 while(scanf("%d",&n)!=EOF&&n){ 30 scanf("%d",&q); 31 for(int i=1;i<=n;i++) scanf("%d",a+i); 32 for(int i=1;i<=n;i++){ 33 if(a[i]==a[i-1]) b[i]=b[i-1]+1; 34 else b[i]=1; 35 } 36 rmq(n); 37 while(q--){ 38 int t1,t2,t=0; 39 scanf("%d%d",&t1,&t2); 40 t=t1; 41 while(t<=t2&&a[t]==a[t-1]) t++; 42 int maxres=query(t,t2); 43 maxres=max(maxres,t-t1); 44 printf("%d ",maxres); 45 } 46 } 47 return 0; 48 }