RMQ问题中的ST算法
长为 n 的数组 a ，m次询问，求l~r中最大值是多少
// RMQ问题中的ST算法
// m次询问，求l~r中最大值是多少
#include<bits/stdc++.h>
#define reg register
using namespace std;
// 读取输入的函数
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
// 输出结果的函数
inline void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
const int MAXN=100005;
vector<int > a; // 存储输入数据的数组
int n,f[MAXN][21],m; // f[i][j]表示区间[i, j]的最大值
// ST预处理函数
void ST_prework(){
for(reg int i=1;i<=n;i++) f[i][0]=a[i]; // 将第一个元素作为区间的最大值
int t=log(n)/log(2)+1; // 确定二维数组f的维度
for(reg int j=1;j<t;j++){ // 从第二个维度开始遍历二维数组f
for(reg int i=1;i<=n-(1<<j)+1;i++){ // 从第一个维度开始遍历一维数组f的第一部分
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); // 根据状态转移方程更新f[i][j]的值
}
}
return ;
}
// ST查询函数，返回区间[l, r]的最大值
int ST_query(int l, int r){
int g=log(r-l+1)/log(2); // 计算区间长度的对数，向上取整得到二进制位数g
return max(f[l][g],f[r-(1<<g)+1][g]); // 根据状态转移方程和边界条件返回区间最大值
}
// 主函数，读取输入数据，调用ST预处理函数和查询函数，输出结果
int main(){
n=read(),m=read(); // 读取输入数据的数量n和查询次数m
a.push_back(0); // 在a数组末尾添加一个元素，用于记录空元素的位置，方便后续处理边界情况
for(reg int i=1;i<=n;i++)a.push_back(read()); // 按照顺序读取输入数据并存储到a数组中
ST_prework(); // 对输入数据进行预处理，构建ST表f
for(reg int i=1;i<=m;i++){ // 对于每次查询，调用ST查询函数并输出结果
int p=read(),q=read(); // 读取查询的起始位置p和结束位置q
write(ST_query(p, q)); // 将查询结果写入输出流中，并换行分隔每个查询结果
putchar('\n'); // 在每次查询后换行，使得输出更加清晰易读
}
return 0;
}