首页 > 代码库 > RMQ——蒜头君的玩具娃娃(区间范围最大值-区间范围最小值)
RMQ——蒜头君的玩具娃娃(区间范围最大值-区间范围最小值)
蒜头君有 N 个玩具娃娃,编号依次从 1 到 N,每个娃娃都有自己的高度值。蒜头君想考考聪明的你,蒜头君会有 Q 次询问,每次询问给定两个整数 A 和 B,求问编号 A 和编号 B 之间(包含编号 A 和编号 B),高度最大的娃娃和高度最小的娃娃差是多少。
输入格式
第一行输入两个正整数 N,Q(N≤50,000,Q≤200,000)。代表 N 个玩具娃娃,以及蒜头君的 Q 次 询问。
接下来输入 N 行,每行输入一个正整数 h?i??(1≤h?i??≤1,000,000),表示第i 个玩具的高度。
再接下来输入 Q 行,每行输入两个正整数 A 和 B,表示一共有 Q 次询问,每次询问的区间 [A,B](1≤A≤B≤N)。
输出格式
输出一共 Q 行,每行输出一个整数,表示第 i 询问的结果,即区间内高度最大的娃娃和高度最小的娃娃差。
样例输入
5 2 3 1 5 2 7 2 3 1 5
样例输出
4 6
RMQ模板题
l[i][j]表示以i为起点的区间大小为2^j的区间中的最大值。可以用递推求出。
注意‘<<’的优先级没有‘-’高
#include <cstdio> #include <algorithm> #include <iostream> using namespace std; const int maxn=50000+10; int a[maxn]; int n; int s[maxn][50];//存储最小值 int l[maxn][50];//存储最大值 void rmg_init() { for(int i=0;i<n;i++) s[i][0]=l[i][0]=a[i]; for(int j=1;(1<<j)<=n;j++)//先枚举区间范围 for(int i=0;i<n;i++) { s[i][j]=min(s[i][j-1],s[i+(1<<j-1)][j-1]);//<<没有-的优先级高 l[i][j]=max(l[i][j-1],l[i+(1<<j-1)][j-1]); } } int query(int x,int y) { int fl,fs; int k=0,t=y-x+1; while(1<<k<=t) k++; k--; fs=min(s[x][k],s[y-(1<<k)+1][k]); fl=max(l[x][k],l[y-(1<<k)+1][k]); return fl-fs; } int main() { int q; cin>>n>>q; for(int i=0;i<n;i++) cin>>a[i]; rmg_init(); while(q--) { int x,y; cin>>x>>y; int ans=query(x-1,y-1); cout<<ans<<endl; } return 0; }
RMQ——蒜头君的玩具娃娃(区间范围最大值-区间范围最小值)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。