题目： P3865 【模板】ST表
代码实现
// ST表
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
int f[31][100005];//f用来记录区间最大值：从 j 开始长度为 2^i 的区间
int logg[100005];
int n, m;
void Build_ST()
{
for (int i = 1; i <= 19; i++)
for (int j = 1; j + (1<<i) - 1 <= n; j++)//枚举长度
f[i][j] = max ( f[i-1][j], f[i-1][j + (1<<(i-1))] );//也可以先用数组预处理 2 ^ i 的值
}
int findd (int l, int r)
{
if(!logg[r - l + 1])//log 也预处理一下
logg[r - l + 1] = log2(r - l + 1);
int k = logg[r - l + 1];
return max (f[k][l], f[k][r - (1<<k) + 1]);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i = 1; i <= n; i++)
scanf("%d",&f[0][i]);
Build_ST();//建表
for (int i = 1; i <= m; i++)
{
int l, r;
scanf ("%d%d",&l,&r);//查找
printf ("%d\n", findd (l, r));
}
return 0;
}
注：可能出现 TLE 的情况，需要手写快读
