大致题意:
给出一列共n个数,m次询问。每次询问包括两个数a,b。输出区间[a,b]中最大值与最小值的差。
大致思路:
RMQ区间极值求法的模版题。
以下内容转自:http://www.cnblogs.com/cnjy/archive/2009/08/30/1556566.html
RMQ(Range Minimum/Maximum Query)问题:
RMQ问题是求给定区间中的最值问题。当然,最简单的算法是O(n)的,但是对于查询次数很多(设置多大100万次),O(n)的算法效率不够。可以用线段树将算法优化到O(logn)(在线段树中保存线段的最值)。不过,Sparse_Table算法才是最好的:它可以在O(nlogn)的预处理以后实现O(1)的查询效率。下面把Sparse Table算法分成预处理和查询两部分来说明(以求最小值为例)。
预处理:
预处理使用DP的思想,f(i, j)表示[i, i+2^j - 1]区间中的最小值,我们可以开辟一个数组专门来保存f(i, j)的值。
例如,f(0, 0)表示[0,0]之间的最小值,就是num[0], f(0, 2)表示[0, 3]之间的最小值, f(2, 4)表示[2, 17]之间的最小值
注意, 因为f(i, j)可以由f(i, j - 1)和f(i+2^(j-1), j-1)导出, 而递推的初值(所有的f(i, 0) = i)都是已知的
所以我们可以采用自底向上的算法递推地给出所有符合条件的f(i, j)的值。
查询:
假设要查询从m到n这一段的最小值, 那么我们先求出一个最大的k, 使得k满足2^k <(n - m + 1).
于是我们就可以把[m, n]分成两个(部分重叠的)长度为2^k的区间: [m, m+2^k-1], [n-2^k+1, n];
而我们之前已经求出了f(m, k)为[m, m+2^k-1]的最小值, f(n-2^k+1, k)为[n-2^k+1, n]的最小值
我们只要返回其中更小的那个, 就是我们想要的答案, 这个算法的时间复杂度是O(1)的.
例如, rmq(0, 11) = min(f(0, 3), f(4, 3))
由此我们要注意的是预处理f(i,j)中的j值只需要计算log(n+1)/log(2)即可,而i值我们也只需要计算到n-2^k+1即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int nMax= 50003;
int num[nMax],n;
int maxMap[nMax][20];
int minMap[nMax][20];
void maxRmq(){ //map(i, j)表示[i, i+2^j - 1]区间中的最值
int i,j;
for(i=1;i<=n;i++){
maxMap[i][0]=num[i];
}
for(j=1;j<=log((double)(n+1))/log(2.0);j++){
for(i=1;i+(1<<j)-1<=n;i++){
maxMap[i][j]=max(maxMap[i][j-1],maxMap[i+(1<<(j-1))][j-1]);
}
}
}
void minRmq(){
int i,j;
for(i=1;i<=n;i++){
minMap[i][0]=num[i];
}
for(j=1;j<=log((double)(n+1))/log(2.0);j++){
for(i=1;i+(1<<j)-1<=n;i++){
minMap[i][j]=min(minMap[i][j-1],minMap[i+(1<<(j-1))][j-1]);
}
}
}
int askMax(int a,int b){
if(a>b)swap(a,b);
int k =(int)(log((double)(b-a+1))/log(2.0));
return max(maxMap[a][k],maxMap[b-(1<<k)+1][k]);
}
int askMin(int a,int b){
if(a>b)swap(a,b);
int k=(int)(log((double)(b-a+1))/log(2.0));
return min(minMap[a][k],minMap[b-(1<<k)+1][k]);
}
int main(){
int m,i,j,a,b;
while(scanf("%d%d",&n,&m)!=EOF){
for(i=1;i<=n;i++)scanf("%d",&num[i]);
maxRmq();
minRmq();
while(m--){
scanf("%d%d",&a,&b);
printf("%d\n",askMax(a,b)-askMin(a,b));
}
}
return 0;
}
分享到:
相关推荐
RMQ以及LCA:最近公共祖先 解析及P解法 (ZFrom Internet)
rmq-docker-win docker build -t gsxsolutions/rmq:3.5.4 -f .\Dockerfile.3.5.4 . docker build -t gsxsolutions/rmq:3.7.4 -f .\Dockerfile.3.7.4 . docker build -t gsxsolutions/rmq:3.7.5 -f .\Dockerfile....
RMQ 动画 这是用于创建文档中说明的动画的应用程序。 这个 repo 是一个简单的应用程序,用于说明 RMQ 可用的动画: rmq(my_view).animations.fade_in rmq(my_view).animations.fade_out rmq(my_view).animations....
RMQ.io 您是否要构建可靠且易于编码的连接服务?Rmq.io的任务rmq.io的任务是使RabbitMQ的发布订阅变得容易1,2,3基本原理一个可靠且简单的pubsub并不容易找到。 RabbitMQ是功能强大的消息队列,它具有许多功能,对于...
简单的 Rabbit MQ 示例 一个使用 Erlang 客户端库的非常简单的 Rabbit MQ 示例 ... 克隆 rmq_simple cd rmq_simple 使 RABBITMQ_VERSION={Version} 依赖 编译 跑起来 享受 :grinning_face_with_smiling_eyes: !
RMQ问题是指:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在[i,j]里的最小值下标。
已完成:天真RMQ,更快RMQ(使用nlogn稀疏表) 待办事项:执行±1 RMQ 天真的RMQ输出: (1(2(4..)(5..))(3(6..)(7..))) indexs : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, values : [1, 2, 4, 2, 5, 2, 1, 3,...
2015_ble_to_rmq ble_to_rmq sample说明: 将此程式编译过的jar档放到respberry pi上执行,可以搜寻附近的BLE Device并与之连接,将透过dongle送到respberry pi的ble讯息印出来。
最全的RMQ资料,看懂了应该RMQ没问题了
| rmq-service | RMQ服务接口实现、基础消息服务接口实现、消息管理子系统服务接口实现 | | rmq-schedule-api | 消息确认子系统、消息恢复子系统服务接口 | | rmq-schedule | 消息确认子系统,与上游业务系统确认...
GACHA_RMQ_CONNECTION_STRING: Connection string for RabbitMQ server GACHA_RMQ_CHANNEL: Binding channel for RabbitMQ GACHA_MYSQL_CONNECTION_STRING: Connection string for local MySQL server, of the form ...
我们会学到RMQ到底是什么东西,并且会知道这样时候的LCA怎么求解,一切尽在其中!
关于RMQ和LCA的关系的知识,如何用RMQ和LCA的转换
注意:我们最近更新了rmq,以显示Redis错误而不是惊慌失措。 这是一个重大更改,因为几乎所有函数现在都返回错误。 建议切换到新版本rmq/v3这样rmq不会因Redis错误而使您的服务崩溃。 如果您还不想升级,则可以继续...
郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 国家队论文
RMQ-MicroService-Base 从rabbitmq微服务中删除锅炉板的基本模块。 var svc = require ( 'rmq-microservice-base' ) ; svc ( { SERVER : 'amqp://localhost' , QUEUE : 'foo.bar' } , function ( job , ack ) {...
rmq算法,有详细注释 dp1[i][j] = max ( dp1[i][j-1] , dp1[i+(1(j-1))][j-1] ) ; dp2[i][j] = min ( dp2[i][j-1] , dp2[i+(1(j-1))][j-1] ) ;
上海人民RMQ6 系列自动转换开关产品样本201512pdf,
ACM中的RMQ和LCA问题 对一个区间的最小值询问,也可以是最大值
这是一个关于后缀数组的与RMQ、LCP有关的资料。。。