本文主要是介绍RMQ小结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
RMQ小结
区间求值得算法主要有三种：
一、处理O（N），查询O（N*Q） (朴素)
二、处理O(log N),查询（QlogN） (线段树)
三、处理O(nlogn),查询（1） （RMQ）
而我们主要来讲一下，O(nlogn)-O(1)的RMQ算法。而RMQ算法的实现又有多种算法，我就选了一种性价比最高的讲解。就是代码容易，时间也可以的算法。因为正宗的RMQ的时间是O(N)-O(1)，我主要说的是ST算法O(NlogN)-O(1)的算法。
RMQ的本质思想是动态规划。度娘如是解释：
#include <iostream>
#include <cstdio>
#include <cmath>
#include<algorithm>
#define MN 50005
using namespace std;
int mi[MN][17],mx[MN][17],w[MN];
int n,q;
void rmqinit()
{int i,j,m;for(i=1;i<=n;i++){mi[i][0]=mx[i][0]=w[i];}int m = int(trunc(log2(n)));for(i=1;i<=m;i++){for(j=n;j>=1;j--){mx[j][i]=mx[j][i-1];if(j+(1<<(i-1))<=n)mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);mi[j][i]=mi[j][i-1];if(j+(1<<(i-1)<=n))mi[j][i]=min(mi[j][i],mi[j+(1<<(i-1))][i-1]);}}
}int rmqmin(int l,int r)
{int m=int(trunc(log2(r-l+1)));return min(mi[l][m],mi[r-(1<<m)+1][m]);
}int rmqmax(int l,int r)
{int m=int(trunc(log2(r-l+1)));return max(mx[l][m],mx[r-(1<<m)+1][m]);
}int main()
{cin>>n>>q;for(int i=1;i<=n;i++)scanf("%d",&w[i]);//cin>>w[i];rmqinit();int l,r;for(int i=1;i<=q;i++){scanf("%d%d",&l,&r);//cin>>l>>r;printf("%d %d\n",rmqmax(l,r),rmqmin(l,r));//cout<<rmqmax(l,r)<<" "<<rmqmin(l,r)<<endl;}while(cin>>n)return 0;
}#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;const int N = 2e5 + 5;
int n,dp[N][20];void RMQ_init()
{int m = int(trunc(log2(n)));
// int m = (int)(log10(n*1.0)/log10(2.0));for(int j = 1;j <= m;++j)for(int i = 1;i+(1<<j)-1 <= n;i++)dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int RMQ(int L,int R)
{
// int k = (int)(log10(R-L+1)*1.0/log10(2.0));int k = int(trunc(log2(R-L+1)));return max(dp[L][k],dp[R-(1<<k)+1][k]);
}
int main()
{int k;while(scanf("%d%d",&n,&k),(n>=0&&k>=0)){int sum = 0,maxv = 0;for(int i = 1;i <= n;++i){scanf("%d",&dp[i][0]);sum += dp[i][0];maxv = max(maxv,dp[i][0]);}if(sum <= k){puts("-1");continue;}RMQ_init();int ans = n,st = k/maxv;if(!st) st++; //注意出现除0的情况---->Runtime Error!!!!!!!!!!!!!!for(int i = st;i < n;++i) //枚举组数{int seg,s = 0;seg = n/i; //可以分成几个区间for(int j = 1;j <= i;j++) //在i个区间内,各个区间的起点和终点{s += RMQ((j-1)*seg+1,j*seg);if(s > k)break;}if(s > k){ans = i;break;}}printf("%d\n",ans);}return 0;
}
AMagic Lamp
题目链接：Click Here~
题意解析：
题目要求，给出一个字符串。让你在删除m个字符之后，求剩下的数组成的最小数是多少。(同理，求剩下的数组成的最大数也是同样的解法)
思路解析：
显然，要删除m个数则原字符串比剩下n-m个（原字符串长度为n）.则，我们知道当两个数的位数相同的时候，就要比较他的首位。
比如，1999与2000.因此，我们要尽量的使首位变小。而这只要在一个区间中找出最小的那个就好了。而问题有出现了，要怎么确定去区间呢？显然，我们在找第一位的时候，后面肯定要至少剩下n-m-1个数。且我们假设我们找到的第一位索引为i1。则第二位的区间可以很容易的确定是从i+1为起点后面至少剩下n-m-2个的区间内。同理，后面的都是相同的道理。
而我们知道区间求极值，我们又可以使用RMQ求得最值。而当运用RMQ的时候我们又可以从逆向思维来考虑。当我们找第一位的时候既然后面要剩下n-m-1个，那不是说明第一位的最值一定是在[0,m]内，第二个在[i1,m+1]呢,ect？这是显然的。所以，我们可以轻松的运用RMQ求出每个区间的最值是多少。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;const int N = 1e3 + 5;
int n,pos[N][20];
char str[N];
void RMQ_init()
{for(int i = 0;i <= n;++i) pos[i][0] = i;int m = int(trunc(log2(n)));for(int j = 1;j <= m;++j)for(int i = 0;i +(1<<j)-1 <= n;++i){int s1 = pos[i][j-1];int s2 = pos[i+(1<<(j-1))][j-1];pos[i][j] = str[s1]<=str[s2]?s1:s2;}
}
int RMQ(int L,int R)
{int m = int(trunc(log2(R-L+1)));int s1 = pos[L][m];int s2 = pos[R-(1<<m)+1][m];return str[s1] <= str[s2]?s1:s2;
}
int main()
{int m;while(~scanf("%s%d",str,&m)){n = strlen(str); // printf("str ---> %s n -- > %d\n",str,n);RMQ_init();
// char res[N];bool first = true;int index,idx = 0,j = m;
// memset(res,'\0',sizeof(res));for(int i = 1;i <= n-m;++i){index = RMQ(idx,j);j++;if(first&&str[index]!='0'){first = false;putchar(str[index]);}else if(!first){putchar(str[index]);}idx = index+1;}if(first) putchar('0');putchar('\n');}return 0;
}
Max Sum of Max-K-sub-sequence
也可以运用单调队列。Click Here~
这篇关于RMQ小结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
