生活随笔
收集整理的这篇文章主要介绍了
RMQ问题
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
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问题的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
