BMQ問題就是在一系列連續的數中，找出一個區間內最小的數，基本思路就是用d[i][j]表示從i開始，長度為2^j的一段元素中的最小值，直接先遞推預處理，時間是O(nlogn)，查找就O(1)

基本模板：

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int maxn = 10000; int d[maxn][maxn];void RMQ_init(int a[], int n) {for (int i = 0; i < n; i++)d[i][0] = a[i];for(int j=1;(1<<j)<=n;j++)for (int i = 0; i + (1 << j)<= n; i++){d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);} } int RMQ(int L, int R) {int k = 0;while ((1 << (k + 1)) <= R - L + 1)k++;return min(d[L][k], d[R - (1 << k) + 1][k]); }int main() {int n;int a[maxn];scanf("%d", &n);for (int i = 0; i < n; i++)scanf("%d", &a[i]);RMQ_init(a,n);printf("%d\n", RMQ(1, 7));return 0; }

例題8 UVa11235

題意：
看白書
要點：
一開始先進行游碼編程，可以看出最左邊和右邊是沒有辦法進行預處理的，因為可能只截取了一半，所以我們將兩個邊界l，r的左右邊界記錄下來特殊處理，中間的直接RMQ即可。

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int maxn = 100005; int coun[maxn], num[maxn], Left[maxn], Right[maxn]; int tot,n,q,a,last; int dp[maxn][25];void RMQ_init() {for (int i = 1; i <= tot; i++) dp[i][0] = coun[i];for (int j = 1; (1 << j) <= tot; j++)for (int i = 1; i + (1 << j) <= tot; i++)dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]); } int RMQ(int L, int R) {if (L > R)return 0;int k = 0;while ((1 << (k + 1)) <= R - L + 1) k++;return max(dp[L][k], dp[R - (1 << k) + 1][k]); }int main() {while (~scanf("%d", &n)&&n){scanf("%d", &q);tot = 0;memset(num, 0, sizeof(num));memset(coun, 0, sizeof(coun));memset(Left, 0, sizeof(Left));memset(Right, 0, sizeof(Right));memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; i++){scanf("%d", &a);if (i == 1){tot++;Left[tot]++;last = a;}if (last == a){num[i] = tot;Right[tot]++;coun[tot]++;}else{num[i] = ++tot;coun[tot]++;Left[tot] = Right[tot] = i;last = a;}}RMQ_init();int l, r;for (int i = 1; i <= q; i++){scanf("%d%d", &l, &r);if (num[l] == num[r])printf("%d\n", r - l + 1);elseprintf("%d\n", max(RMQ(num[l] + 1, num[r] - 1), max(r-Left[num[r]] + 1, Right[num[l]] - l + 1)));}}return 0; }

轉載于:https://www.cnblogs.com/seasonal/p/10343662.html

總結

以上是生活随笔為你收集整理的RMQ问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。