题目描述
给定一个长度为 NN 的数组 aa，其值分别为a1,a2,...,aN。
现有 Q 个询问，每个询问包含一个区间，请回答该区间的最大值为多少。
输入描述
输入第 1行包含两个正整数 N,Q，分别表示数组 aa 的长度和询问的个数。
第 2 行包含 N 个非负整数 a1,a2,...,aN，表示数组 aa 元素的值。
第 3∼Q+2 行每行表示一个询问，每个询问包含两个整数 L,R，表示区间的左右端点
输出描述
输出共 Q 行，每行包含一个整数，表示相应询问的答案。
输入输出样例
示例 1
输入
5 5 1 2 3 4 5 1 1 1 2 1 3 3 4 2 5
输出
1 2 3 4 5
运行限制
最大运行时间：3s最大运行内存: 512M
思路：
首先介绍一个数学原理：
一个大区间若能被两个小区间覆盖，那么大区间的最值等于两个小区间的最值
那么根据这个原理我们可以得到st算法的思路：
把整个数列分为很多小区间，并提前计算出每个小区间的最值；
对任意一个区间最值查询，找到覆盖它的两个小区间，用两个小区间的最值算出答案。
回到我们这道题，对数列的每个元素，把从它开始的数列分成长度为1、2、4、8、…的小区间。下图给出了一个分区的例子，它按小区间的长度分成了很多组。
第 1 组是长度为 1 的小区间，有 n 个小区间，每个小区间有 1 个元素；第 2 组是长度为 2 的小区间，有 n 个小区间，每个小区间有 2 个元素；第 3 组是长度为 4 的小区间，有 n 个小区间，每个小区间有 4 个元素；⋯ 共有 log2（n） 组。
我们发现每组的小区间的最值，可以从前一组递推而来。例如第 33 组 {4, 7, 9, 64,7,9,6} 的最值，可以从第 22 组 {4, 74,7}、{9, 69,6} 的最值递推得到。 我们用dp[x][y]代表左端点是x,区间长度是2^k的区间最大值或者最小值，可以得到递推公式：
那么我们只要遍历每一组并在遍历的过程中存储相应的值，即可得到以题目数据范围内的x为起点，区间长度为2^k的最值了。
题目给定了我们一个区间【L，R】，我们可以先算出这个区间的上两个覆盖他的小区间的最值，再根据公式求出我们要的值。具体见注释
代码：
from math import *
n,m=map(int,input().split())
b=list(map(int,input().split()))
maxn=100001
a=[0]*maxn
for i in range(1,n+1):
a[i]=b[i-1]
#创建40列，maxn行的二维数组数组dp[x][y]，并初始化
#dp[x][y]代表左端点是x,区间长度是2^k的区间最大值或者最小值
dp_max=[[0] * 40 for row in range(maxn)]
#从初始长度为1的小区间开始递推
for i in range(1,n+1):
dp_max[i][0]=int(a[i])
#求得区间长度的2的对数，目的是限制k的范围
#使得2^k2^k<(R-L+1),可用下式求k
k=int(log2(R-L+1))
#通过前两个小区间是相互覆盖的，因此可有他们的最值计算我们要求的最值
return max(dp_max[L][k],dp_max[R-(1<
特别感谢：
https://blog.csdn.net/m0_51951121/article/details/122676209
以及蓝桥杯罗老师的教程
