<题目链接>
题目大意：
给你一个长度为n的序列，这个序列每个数都有一个值，接下来进行q次询问，问在指定区间内出现次数最多的数出现了几次。
解题分析：
因为该序列是非降序的，所以该序列中的所有相等的数都是连续的，因此，我们可以先用dp预处理一下，dp[i]表示以第i个数结尾的最大连续相等个数，于是，本题目就变成了，在指定区间内，dp[i]的最大的值是多少。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; const int M =1e5+;
int st[M][],dp[M],val[M];
int n,q;
void RMQ_init(){
for(int i=;i<=n;i++) //初始化
st[i][]=dp[i];
int k=log((double)(n+))/log(2.0);
for(int j=;j<=k;j++) //用倍增预处理ST表
for(int i=;i+(<<j)-<=n;i++)
st[i][j]=max(st[i][j-],st[i+(<<(j-))][j-]); //倍增递推式
}
int RMQ(int l,int r){
if(l>r)return ;
int k=log((double)(r-l+))/log(2.0);
return max(st[l][k],st[r-(<<k)+][k]);
}
int main(){
while(scanf("%d",&n)!=EOF,n){
scanf("%d",&q);
dp[]=;
for(int i=;i<=n;i++){
scanf("%d",&val[i]);
if(i>)dp[i]=(val[i]==val[i-]?dp[i-]+:); //dp[i]表示以第i个数结尾的最大连续相等个数
}
RMQ_init();
while(q--){
int l,r;
scanf("%d%d",&l,&r);
int tmp=l; //因为dp[i]表示以第i个数结尾的最大连续相等个数，而这里规定了区间的左下标，所以要对该区间与第一个值相同数的个数进行特殊处理，不能直接套用原来预先得到dp[l]
while(tmp<=r&&val[tmp]==val[tmp-])tmp++;
printf("%d\n",max(RMQ(tmp,r),tmp-l));
}
}
return ;
}
2018-10-19
