给定一个长度为 (N) 的数列，和 (M) 次询问，求出每一次询问的区间([l,r])内数字的最大值。
说明
对于30%的数据，满足： (1 leq N, M leq 10 , 1≤N,M≤10)
对于70%的数据，满足： (1 leq N, M leq {10}^5 , 1≤N,M≤10^5)
对于100%的数据，满足： (1 leq N leq {10}^5, 1 leq M leq {10}^6, a_i in [0, {10}^9], 1 leq l_i leq r_i leq N 1≤N≤10^5 ,1≤M≤10^6,a i ∈[0,10^9],1≤l i ≤r i ≤N)
思路
1.(O(n))暴力枚举
左转右转都可以 详情见数据范围
2.线段树(O(logn))
左转右转都可以 详情见数据范围
所以呢，我们需要一个(O(1))的查询效率。
3.区间动规
记录(f(i,j))为区间([i,j])的最大值。
转移(f(i,j)=max(f(i,j−1),a[j]))
然而这需要(O(n^2))的预处理。
左转右转都可以 详情见数据范围
4.ST表
其实这是个经典的ST表模板。静态区间最值。
和LCA一样，都用到了倍增的思路。
我们令(f(i,j)) 为从(a[i])开始的，连续 (2^j)个数的最大值
于是我们有(f(i,0)=a[i])（多显然啊qwq）
于是我们还有(f(i,j)=max(f(i,j-1),f(i+2^{j-1},j-1)))
我太懒了不想证怎么办（画个图膜你一下就行了）
对于查询，根据(max) 的性质，我们可以把区间拆成两个相重叠的区间。
于是按照预处理来推一下就得到，查询区间([left,right])
(len=log2(right-left+1))
(max(f[left][len-1],f[right-(1<<(len-1))+1][len-1])))
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAXN 100005
#define len lg[right-left+1]
#define scan(a) scanf("%d",&a)
#define print(a) printf("%d",a)
#define printn(a) printf("%d
",a)
#define printwn(a) printf("%d ",a)
#define endl printf("
")
using namespace std;
int n,m,a[MAXN],lg[MAXN],maxx[MAXN][25];
int main()
{
scan(n); scan(m);
for (int i=1;i<=n;i++)
{
lg[i]=lg[i/2]+1;
}
for (int i=1;i<=n;i++)
{
scan(a[i]);
}
for (int i=1;i<=n;i++)
{
maxx[i][0]=a[i];
}
for (int i=1;i<=lg[n];i++)
{
for (int j=1;j+(1<<i)-1<=n;j++)
{
maxx[j][i]=max(maxx[j][i-1],maxx[j+(1<<(i-1))][i-1]);
}
}
int left,right;
for (int i=1;i<=m;i++)
{
scan(left); scan(right);
printn(max(maxx[left][len-1],maxx[right-(1<<(len-1))+1][len-1]));
}
return 0;
}