简单的RMQ(RMQ+ST NEUQ“图灵杯”)
题目描述
给定一个数组，其中的元素满足非递减顺序。任意给定一个区间[i,j]，求其中某个元素重复出现的最大次数。
输入
多组数据输入。每组数据的第一行包含两个整数n和q(1<=n,q<=100000)，下一行包含n个整数a1,...,an(-100000<=ai<=100000,i∈{1,...,n})，用空格分隔，数列是升序的(ai<=ai+1)。接下来的q行，每行包含两个整数i和j(1<=i<=j<=n)，表示给定区间[i,j]。
输入结束于0(自成一行)。
输出
对输入的q个区间，每个区间输出一个整数表示该区间内重复最多的元素出现的次数，用换行分隔。
样例输入
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0 样例输出
1
4
3 #include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#define MAX 100005
using namespace std;
int stTable[MAX][20];
int num[MAX];
int sum[MAX];
int n,q,ans,a,b;
void Build_ST()
{
for(int i=1;i<=n;i++)
stTable[i][0]=sum[i];
int k=log((double)(n+1))/log(2.0);
for(int i=1;i<=k;i++)
for(int j=1;j+(1<<i)<=n+1;j++)
stTable[j][i]=max(stTable[j][i-1],stTable[j+(1<<(i-1))][i-1]);
}
int RMQ_Query(int l,int r)
{
if(l>r)return 0;
int k=log((double)(r-l+1))/log(2.0);
return max(stTable[l][k],stTable[r-(1<<k)+1][k]);
}
int main()
{
while(scanf("%d",&n)!=EOF,n)
{
sum[1]=1;
scanf("%d",&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
if(i==1)continue;
if(num[i]==num[i-1])sum[i]=sum[i-1]+1;
else sum[i]=1;
}
Build_ST();
while(q--){
scanf("%d%d",&a,&b);
if(a==b||num[a]==num[b]){
cout<<b-a+1<<endl;
continue;
}
int t=a;
while(num[t]==num[t-1]&&t<=b)
t++;
int cnt=RMQ_Query(t,b);
ans=max(cnt,t-a);
printf("%d\n",ans);
}
}
return 0;
}
/**************************************************************
Problem: 1760
User: T227
Language: C++
Result: 正确
Time:1488 ms
Memory:10136 kb
****************************************************************/
投递美团等公司6个岗位 >
