一. 倍增
RMQ 问题(Range Minimum/Maximum Query,区间最值问题):给定长度为 n 的静态数列,做 m次询问,每次给定 【L,R】,查询区间[L, R]内的最值。
ST 算法两个步骤:
把整个数列分为很多小区间,并提前计算出每个小区间的最值;
对任意一个区间最值查询,找到覆盖它的两个小区间,用两个小区间的最值算出答案。
//区间最大值 #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<math.h> using namespace std; const int N = 5e5 + 10; int a[N]; int dp[N][35]; //dp[s][k] 表示 左端点是s,区间长度是2^k【s,s+2^k-1】的最值 int n,q; void initia() { //初始化 for(int i = 1; i <= n; i++)dp[i][0] = a[i]; int k_max = log2(n); for(int k = 1; k <= k_max; k++) for(int s = 1; s + (1 << k) - 1 <= n; s++) dp[s][k] = max(dp[s][k-1],dp[s+(1 << (k-1))][k-1]); } int check(int l, int r) { int len = r - l + 1; int tip = log2(len); return max(dp[l][tip],dp[r + 1 - (1<<tip)][tip]); } int main() { cin >> n >> q; for(int i = 1; i <= n; i++)cin >> a[i]; initia(); int l = 0; int r = 0; while(q--) { cin >> l >> r; cout << check(l , r) << endl; } return 0; }