hdu 1806 Frequent values(给定一个非降序数组，求任意区间内出现次数最多的数的次数)
最后更新于：2022-04-01 16:02:08
**1.题目解析可见《训练指南》P198**
**2代码：**
~~~
#include<cstdio>
#include<cstring>
#include<cmath>
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define N 100005
#define INF 1<<30
using namespace std;
int a[N];
int value[N],cnt[N],num[N],L[N],R[N];
int ST[N][20];
int n,q;
int k;
void make_ST()//对cnt[]预处理
{
for(int i=1;i<=k;i++)
{
ST[i][0]=cnt[i];
}
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;(i+(1<<j)-1)<=n;i++)
{
ST[i][j]=Max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
}
}
}
int Query(int l,int r)
{
if(l>r)
return 0;
else
{
int kk=floor(log2(r-l+1));
return Max(ST[l][kk],ST[r-(1<<kk)+1][kk]);
}
}
int main()
{
while(scanf("%d",&n)&&n)
{
scanf("%d",&q);
k=0;
value[0]=INF;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]!=value[k])
{
R[k]=i;
value[++k]=a[i];
L[k]=i-1;
cnt[k]=1;
num[i]=k;
}
else
{
cnt[k]++;
num[i]=num[i-1];
}
}
R[k]=n+1;
make_ST();
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
if(num[l]==num[r])
{
printf("%d\n",r-l+1);
}
else
{
int tmp=Max(R[num[l]]-l,r-L[num[r]]);
int ans=Max(tmp,Query(num[l]+1,num[r]-1));
printf("%d\n",ans);
}
}
}
return 0;
}
~~~