hihocoder 1068 RMQ-ST算法如何优化实现？

本文共计396个文字，预计阅读时间需要2分钟。

题目链接：RMQ-ST算法

题目大意：给你一个区间，查询该区间最小值

题目思路：直接使用RMQ+ST

题目链接：​​RMQ-ST算法​​

题目大意：给你一个区间，查询区间最小值

题目思路：直接RMQ

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = 1e6+10;

int N,Q,a[maxn];
int dpmax[maxn][20],dpmin[maxn][20];

void init_RMQ(){
int l = (int)(log(N)/log(2.0));
for(int i = 1;i <= N;i++)
dpmax[i][0] = dpmin[i][0] = a[i];
for(int j = 1;j <= l;j++){
for(int i = 1;i+(1<<j)-1 <= N;i++){
//dpmax[i][j] = max(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]);
dpmin[i][j] = min(dpmin[i][j-1],dpmin[i+(1<<(j-1))][j-1]);
}
}
}

int RMQMax(int l,int r){
int k = (int)(log(r-l+1)/log(2.0));
return max(dpmax[l][k],dpmax[r-(1<<k)+1][k]);
}

int RMQMin(int l,int r){
int k = (int)((log(r-l+1))/(log(2.0)));
return min(dpmin[l][k],dpmin[r-(1<<k)+1][k]);
}


int main(){
while(~scanf("%d",&N)){
for(int i = 1;i <= N;i++) scanf("%d",&a[i]);
init_RMQ();
scanf("%d",&Q);
while(Q--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",RMQMin(l,r));
}
}
return 0;
}