题目描述
给定一个长度为 N 的数组 a，其值分别为a1,a2,...,aN。
现有 Q 个询问，每个询问包含一个区间，请回答该区间的最大值为多少。
输入描述
输入第 1行包含两个正整数 N,Q，分别表示数组 aa 的长度和询问的个数。
第 2 行包含 N 个非负整数 a1,a2,...,aN，表示数组 aa 元素的值。
第 3∼Q+2 行每行表示一个询问，每个询问包含两个整数 L,R，表示区间的左右端点
输出描述
输出共 Q 行，每行包含一个整数，表示相应询问的答案。
输入输出样例
示例 1
输入
1. 5 5 2. 1 2 3 4 5 3. 1 1 4. 1 2 5. 1 3 6. 3 4 7. 2 5
输出
1. 1 2. 2 3. 3 4. 4 5. 5
运行限制
- 最大运行时间：3s
- 最大运行内存: 512M
思路：
首先介绍一个数学原理：
一个大区间若能被两个小区间覆盖，那么大区间的最值等于两个小区间的最值
那么根据这个原理我们可以得到st算法的思路：
- 把整个数列分为很多小区间，并提前计算出每个小区间的最值；
- 对任意一个区间最值查询，找到覆盖它的两个小区间，用两个小区间的最值算出答案。
回到我们这道题，对数列的每个元素，把从它开始的数列分成长度为1、2、4、8、…的小区间。下图给出了一个分区的例子，它按小区间的长度分成了很多组。
- 第 1 组是长度为 1 的小区间，有 n 个小区间，每个小区间有 1 个元素；
- 第 2 组是长度为 2 的小区间，有 n 个小区间，每个小区间有 2 个元素；
- 第 3 组是长度为 4 的小区间，有 n 个小区间，每个小区间有 4 个元素；
- ⋯ 共有 log2（n） 组。
我们发现每组的小区间的最值，可以从前一组递推而来。例如第 3 组 {4, 7, 9, 6} 的最值，可以从第 2 组 {4, 7}、{9, 6} 的最值递推得到。
定义状态：
dp[x][y]代表左端点是x,区间长度是2^k的区间最大值或者最小值
dp_max[s][k]=max(dp_max[s][k-1],dp_max[s+(1<<(k-1))][k-1])
那么我们只要遍历每一组并在遍历的过程中存储相应的值，即可得到以题目数据范围内的x为起点，区间长度为2^k的最值了。
题目给定了我们一个区间【L，R】，我们可以先算出这个区间的上两个覆盖他的小区间的最值，再根据公式求出我们要的值。我们下一步要确定两个小区间的长度
首先区间 [L, R][L,R] 的长度是 len = R-L+1l。设两个小区间的长度都是 x，其中 x 是比 len 小的 2 的最大倍数，有x≤len 且 2×x≥len，这样才保证能覆盖。另外需要计算 dp[][]，根据 dp[s][k] 的定义，有 2^k =x。例如 len = 19，x=162k=16，k=4
在代码中我们可以调用python自带的函数算出k
k=int(log2(R-L+1))
我们在查询中只查询覆盖该区间的两个子区间的最值即可：
return max(dp_max[L][k],dp_max[R-(1<<k)+1][k])
代码：
1. from math import * 2. n,m=map(int,input().split()) 3. b=list(map(int,input().split())) 4. maxn=100001 5. a=[0]*maxn 6. for i in range(1,n+1): 7. a[i]=b[i-1] 8. #创建40列，maxn行的二维数组数组dp[x][y]，并初始化 9. #dp[x][y]代表左端点是x,区间长度是2^k的区间最大值或者最小值 10. dp_max=[[0] * 40 for row in range(maxn)] 11. 12. #从初始长度为1的小区间开始递推 13. for i in range(1,n+1): 14. dp_max[i][0]=int(a[i]) 15. 16. #求得区间长度的2的对数，目的是限制k的范围 17. #使得2^k<n，计算出以每一个以s为起点，区间为2^k的最值 18. p=int(log2(n)) 19. for k in range(1,p+1): 20. for s in range(1,n+2-(1<<k)): 21. #后一个区间的最大值可以由覆盖此区间的前两个小区间确定 22. dp_max[s][k]=max(dp_max[s][k-1],dp_max[s+(1<<(k-1))][k-1]) 23. 24. 25. def st_query(L,R): 26. #计算求得我们所求的区间的前两个小区间的长度2^k 27. #因为2^k<(R-L+1),2^(k+1)>2^k<(R-L+1),可用下式求k 28. k=int(log2(R-L+1)) 29. #前两个小区间是相互覆盖的，因此可有他们的最值计算我们要求的最值 30. return max(dp_max[L][k],dp_max[R-(1<<k)+1][k]) 31. 32. for i in range(1,m+1): 33. L,R=map(int,input().split()) 34. print(st_query(L,R))
特别感谢：
https://blog.csdn.net/m0_51951121/article/details/122676209
以及蓝桥杯罗老师的教程
