输入一串数字，给你 MM 个询问，每次询问就给你两个数字 X,YX,Y，要求你说出 XX 到 YY 这段区间内的最大数。
第一行两个整数 N,MN,M 表示数字的个数和要询问的次数；
接下来一行为 NN 个数；
接下来 MM 行，每行都有两个整数 X,YX,Y。
输出共 MM 行，每行输出一个数。
10 2 3 2 4 5 6 8 1 2 9 7 1 4 3 8
5 8
数据范围与提示：
对于全部数据，1≤N≤105,1≤M≤106,1≤X≤Y≤N1≤N≤105,1≤M≤106,1≤X≤Y≤N。数字不超过 C/C++C/C++ 的 intint 范围。
解析： 这是指求区间最值的模板问题，这里采用 ST算法来实现。
倍增思想：
f[i][j]表示i开始的连续2j 个点的最大值。
则f[i][0]表示i开始连续1个点的最大值即a[i];
f[i][1]表示i开始连续2个点的最大值即a[i]和a[i+1]的最大值;
f[i][2]表示i开始连续4个点的最大值即a[i]~a[i+3]中的最大值；
f[i][3]表示i开始连续8个点的最大值即a[i]~a[i+7]中的最大值;
......
f[i][log(n)/log(2)开始连续n个点的最大值即 a[i]~a[i+n-1];(i+n-1<=n)
| f[1][0]=a[1]=3; | f[2][0]=a[2]=2; | f[3][0]=a[3]=4; | f[4][0]=a[4]=5; | f[5][0]=a[5]=6; | f[6][0]=a[6]=8; | f[7][0]=a[7]=1; | f[8][0]=2; | f[9][0]=9; | f[10][0]=7; |
| f[1][1]=max(f[1][0],f[2][0])=3 | f[2][1]=max(f[2][0],f[3][0])=4 | f[3][1]=max(f[3][0],f[4][0])=5 | f[4][1]=max(f[4][0],f[5][0])=6 | f[5][1]=max(f[5][0],f[6][0])=8 | f[6][1]=8 | f[7][1]=2 | |||
| f[1][2]=max(f[1][1],f[3][1])=4 | f[2][2]=max(f[2][1],f[4][1])=6 | f[3][2]=max(f[3][1],f[5][1])=8 | f[4][2]=max(f[4][1],f[6][1])=8 | f[5][2]=max(f[5][1],f[7][1])= 8 | f[6][2]=9 | f[7][2]=9 | |||
| f[1][3]=max(f[1][2],f[5][2])=8 | f[2][3]=max(f[2][2],f[6][2])=9 | f[3][3]=max(f[3][2],f[7][2])=9 | |||||||
#include<iostream> #include<cmath> #include<cstdio> using namespace std; const int maxn=100100; int n,m; int f[maxn][20],a[maxn]; void st(){ int k=log(n)/log(2); for(int i=1;i<=n;i++)f[i][0]=a[i]; for(int j=1;j<=k;j++) for(int i=1;i+(1<<j)-1<=n;i++)//长度为2^j的区间[i,i+2^j-1] f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); } int qwt(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(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); st(); for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); printf("%d\n",qwt(x,y)); } return 0; }
原文：https://www.cnblogs.com/ssfzmfy/p/11167249.html