rmq问题:
先贴一下定义
范围最值查询
*,*的百科全书范围最值查询(Range Minimum Query),是针对数据集的一种条件查询。若给定一个数组 A[1, n],范围最值查询指定一个范围条件 i 到 j,要求取出 A[i, j] 中最大/小的元素。
若 A = [3, 5, 2, 5, 4, 3, 1, 6, 3],条件为 [3, 8] 的范围最值查询返回 1,它是子数组 A[3, 8] = [2, 5, 4, 3, 1, 6]中最小的元素。
通常情况下,数组 A 是静态的,即元素不会变化,例如插入、删除和修改等,而所有的查询是以在线的方式给出的,即预先并不知道所有查询的参数。
RMQ 问题有预处理 O ( n ) {\displaystyle O(n)} 之后每次查询 O ( 1 ) {\displaystyle O(1)} 的算法[1]。
范围最值查询问题(RMQ)与最近公共祖先 (图论)(LCA)问题有直接联系,它们可以互相转化。RMQ 的算法常常应用在严格或者近似子串匹配等问题的处理中。
暴力的去查询,期望复杂度是O(N)查询,O(N)处理
用线段树维护,期望复杂度O(logN)查询,O(N)处理
当然还有更优秀的ST算法(稀疏表算法)
----以上均转自*
相对比线段树维护,st算法可以做到O(1)回答,复杂度有了不少的优化
#pragma GCC optimize("O2")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<limits.h>
#include<ctime>
#define N 100001
typedef long long ll;
const int inf=0x3fffffff;
const int maxn=2017;
using namespace std;
inline int read()
{
int f=1,x=0;char ch=getchar();
while(ch>'9'|ch<'0')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return f*x;
}
int rmq[30][N],lg[N]; void init(int n)
{
for(int i=2;i<=n;i++)
lg[i]=lg[i>>1]+1;
for(int i=1;i<=lg[n];i++)
for(int j=1;j<=n+1-(1<<i);j++)
rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
} int rminq(int l,int r)
{
if(l>r)swap(l,r);
int x=lg[r-l+1];
return min(rmq[x][l],rmq[x][r+1-(1<<x)]);
} int main()
{
int n=read(),m=read();
for(int i=1;i<=n;i++)
rmq[0][i]=read();
for(int i=1;i<=m;i++)
{
int l=read(),r=read();
printf("%d\n",rminq(l,r));
}
}
O ( N l o g N + Q ) {\displaystyle O(NlogN+Q)} ,Q 为查询数。
rmq问题模板处理的更多相关文章
-
poj 3264 Balanced Lineup (RMQ算法 模板题)
RMQ支持操作: Query(L, R): 计算Min{a[L],a[L+1], a[R]}. 预处理时间是O(nlogn), 查询只需 O(1). RMQ问题 用于求给定区间内的最大值/最小值问题 ...
-
RMQ 2d 模板
#include<iostream> #include<cstdio> #include<string.h> #include<string> #inc ...
-
RMQ(模板 ST 区间最值,频繁的间隔时间)
PS: 介绍:http://blog.csdn.net/liang5630/article/details/7917702 RMQ算法.是一个高速求区间最值的离线算法,预处理时间复杂度O(n*log( ...
-
ZOJ 2859 二维RMQ(模板)
这题求范围最小值,RMQ正好是用来解决这方面的.所以再适合只是了,又是离线静态输入输出的,所以时间比二维线段树快. #include<iostream> #include<cstdi ...
-
RMQ算法模板
分别写了下标从0和1开始的两种 #include<stdio.h> #include<string.h> #include<algorithm> #include& ...
-
倍增算法总结 ( 含RMQ模板)
部分题目来自<算法竞赛设计进阶> 问题 给定一个长度为n的数列A,有m个询问,每次给定一个整数T,求出最大的k,满足a[1],a[2]……a[k]的和小于等于T(不会打sigm ...
-
RMQ 模板题 poj 3264
题目:点这里 题意:给一个长度n的数列,然后又Q个询问,问L 到R 中最大值与最小值的差. 分析:RMQ 的模板题. 代码: #include<stdio.h> #include& ...
-
LCA和RMQ
下面写提供几个学习LCA和RMQ的博客,都很通熟易懂 http://dongxicheng.org/structure/lca-rmq/ 这个应该是讲得最好的,且博主还有很多其他文章,可以读读,感觉认 ...
-
RMQ (Range Minimal Query) 问题 ,稀疏表 ST
RMQ ( 范围最小值查询 ) 问题是一种动态查询问题,它不需要修改元素,但要及时回答出数组 A 在区间 [l, r] 中最小的元素值. RMQ(Range Minimum/Maximum Query ...
随机推荐
-
使用html模板
创建html---点击next--选择写好的模板
-
初识 Asp.Net内置对象之Response对象
Response对象 Respose对象用于将数据从服务器发送回浏览器.它允许将数据作为请求的结果发送到浏览器,并提供有光响应的信息,可以用来在页面中输入数据,在页面中跳转,还可以传递各个页面的参数, ...
-
HTML页面中常见的一些小方法
在<Head>标签中加 <meta http-equiv="pragma " content="no-cache"> <met ...
-
js设计模式(10)---观察者模式
0.前言 最近好多烦心事,由于自己的拖延懒惰造成事情堆积如山,看来最近得勤快些了,不然真的会死的很惨. 1.观察者模式是什么 又叫做发布者订阅者模式(publish/Subscribe),用来确定对象 ...
-
[转载]JS对URL的编码
虽然escape().encodeURI().encodeURIComponent()三种方法都能对一些影响URL完整性的特殊字符进行过滤.但后两者是将字符串转换为UTF-8的方式来传输,解决了页面编 ...
-
BrnShop开源网上商城第三讲:插件的工作机制
这几天BrnShop的开发工作比较多,所以这一篇文章来的晚了一些,还请大家见谅呀!还有通知大家一下BrnShop1.0.312版本已经发布,此版本添加了报表统计等新功能,需要源码的园友可以点此下载.好 ...
-
hdoj 2553 N皇后问题【回溯+打表】
N皇后问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submi ...
-
Android NetWorkUtil
package com.android.hcframe.netdisc.util; import java.io.BufferedReader; import java.io.InputStreamR ...
-
eclipse安装lombok插件
1:下载jar https://projectlombok.org/download.html 2:双击下载的lombok.jar 安装 3:如果eclipse没有安装到默认目录,需要手动选择ecli ...
-
Kubuntu定制开始菜单
在我旧的博客(http://blog.sina.com.cn/eltaera)里,曾经转载过关于ubuntu定制的文章(http://blog.sina.com.cn/s/blog_8709e3120 ...