题目描述
输入一串数字,给你 M 个询问,每次询问就给你两个数字 X,Y,要求你说出 X 到 Y 这段区间内的最大数。
输入格式
第一行两个整数 N,M 表示数字的个数和要询问的次数;
接下来一行为 N 个数;
接下来 M 行,每行都有两个整数 X,Y。
输出格式
输出共 M 行,每行输出一个数。
数据范围
1≤N≤105,
1≤M≤106,
1≤X≤Y≤N,
数列中的数字均不超过231−1
样例
输入样例:
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
输出样例:
5
8
题解
就本题,有多种解法,下面运用ST算法为大家写一份题解。
ST算法是倍增的思想上衍生而来的,它可以在给定一个长度为N的序列A,在O(NlogN)的预处理之后,以O(1)的时间复杂度在线回答“数列A中下标在l-r之间的数最大值是多少”这样的问题,是一个非常优秀的算法。
具体算法讲解见《算法竞赛进阶指南》P41。
接下来给出代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
const int M=1e6;
long long n,m,a[N],f[N][20],x,y;
void stwork()
{
for(int i=1;i<=n;i++)
{
f[i][0]=a[i];
}
int t=log(n)/log(2)+1;
for(int j=1;j<t;j++)
for(int i=1;i<=n-(1<<j)+1;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int st(int l,int r)
{
int k=log(r-l+1)/log(2);
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
stwork();
while(m--)
{
scanf("%d%d",&x,&y);
cout<<st(x,y)<<endl;
}
return 0;
}