注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

石门实验中学卢凯宾的博客

向前跑,迎着冷眼和嘲笑。

 
 
 

日志

 
 

RMQ  

2015-12-12 12:18:10|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
RMQ (Range Minimum/Maximum Query)问题是指:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在i,j里的最小(大)值,也就是说,RMQ问题是指求区间最值的问题。”——某百科
看完上面这段文字,我们就可以知道所谓RMQ的作用了。它是一种求区间最值的算法。
简单回忆一下,平时我们求区间最值的时候是怎么做的呢?
对于一般的选手,在没有学过RMQ之前,一般都会第一时间想到用朴素的方法去解决,也就是:
# include <cstdio>

#define max(x,y) x>y?x:y

const int SIZE=3005;

int n , a[SIZE] , m ;

int main () {
	freopen ( "rmq.in" , "r" , stdin ) ;
	freopen ( "rmq.out" , "w" , stdout ) ;
	scanf ( "%d" , &n ) ;
	for ( int i=1 ; i!=n+1 ; ++i )
		scanf ( "%d" , &a[i] ) ;
	scanf ( "%d" , &m ) ;
	for ( int i=0 ; i!=m ; ++i ) {
		int left , right ;
		scanf ( "%d%d" , &left , &right ) ;
		int ans=a[right];
		for ( int j=left ; j!=right ; ++j )
			ans=max(ans,a[j]) ;
		printf ( "%d\n" , ans ) ;
	}
	return 0 ;
}
容易看出,上述算法的时间复杂度达到Θ(n×Qlen),其中Qlen表示每次询问的长度,时间复杂度达到平方级,当n>104时会超时!
RMQ - cxb6lkb - 石门实验中学卢凯宾的博客
 前6组数据1 ≤  n  <  1,000,1 ≤  m  <  100,000。 
 最后4组数据1 ≤  n    3,000,1 ≤  m  <  1,000,000。 

在上述算法的基础上,我们可以进行改进。
由上图可以看出,该算法速度慢的原因主要是每次都求一次区间内的最值,因此询问次数增加时耗时就会快速增长!
我们不妨先把所有可能的区间内最值都预求一遍,用f[i][j]表示区间[i,j]内的最值。

# include <cstdio>

#define max(x,y) x>y?x:y

const int SIZE=3005;

int n , a[SIZE] , m , f[SIZE][SIZE] ;

int main () {
	freopen ( "rmq.in" , "r" , stdin ) ;
	freopen ( "rmq.out" , "w" , stdout ) ;
	scanf ( "%d" , &n ) ;
	for ( int i=1 ; i!=n+1 ; ++i ) {
		scanf ( "%d" , &a[i] ) ;
		f[i][i] = a[i] ;
	}
	for ( int i=1 ; i!=n+1 ; ++i )
		for ( int j=i+1 ; j!=n+1 ; ++j )
			f[i][j] = max ( f[i][j-1] , a[j] ) ;
	scanf ( "%d" , &m ) ;
	for ( int i=0 ; i!=m ; ++i ) {
		int left , right ;
		scanf ( "%d%d" , &left , &right ) ;
		printf ( "%d\n" , f[left][right] );
	}
	return 0 ;
}
上述算法用空间换时间,其优势体现在询问次数特别多的情况下,但预处理的时间复杂度也达到Θ(n2),询问的时间复杂度为θ(1)

RMQ - cxb6lkb - 石门实验中学卢凯宾的博客
 那么问题来了:n总不可能永远10,000,我们面临着1s的严峻考验。
于是,rmq登场了!!
今天介绍的是rmq中的st算法。该算法和刚才算法二的思想差不多,都是靠预处理来实现θ(1)的询问。但是,强大的st算法在预处理时的阶段与算法二不同,f[i][j]表示第i个数起连续2j个数的最值,换言之f[i][j] =min(a[j], a[j+1], …, a[j+2i])
举个栗子:
a={3 2 4 5 6 8 1 2 9 7}
f[1,0]表示第1个数起,长度为20=1的最大值,其实就是3这个数。同理 f[1,1] = max(3,2) = 3, f[1,2]=max(3,2,4,5) = 5,f[1,3] = max(3,2,4,5,6,8,1,2) = 8。
并且我们可以容易的看出f[i,0]就等于a[i]。
根据以上思想容易写出如下预代理部分:
for ( int i=2 ; i!=n+1 ; ++i )
	log2[i] = log2[i>>1]+1 ;
for ( int i=0 ; i!=n ; ++i )
	scanf ( "%d" , f[0][i] ) ;
for ( int i=1 ; i!=log2[n]+1 ; ++i ) {
	for ( int j=0 ; j!=n-(1<<i)+1 ; ++j )
		f[i][j] = max ( f[i-1][j] , f[i-1][j+(1<<(i-1))] ) ;
}
现在我们就顺利地对这些数据进行了预处理,时间复杂度为θ(nlog2n),但大部分情况下(j-i+1)并不一定就刚好是2的正整次幂,怎么查询呢?
其实,我们可以令k=log2j-i+1并(j-i+1)分为两部分,一部分以i为开头,长度为2k;另一部分以j结尾,长度也是2k。两部分最值当中的最大值即为所求。
RMQ - cxb6lkb - 石门实验中学卢凯宾的博客
 代码如下:
# include <cstdio>

int N , M , f[18][500000];

int max ( int a , int b ) {
	return a > b ? a : b ;
}

int main() {
	freopen ( "rmq.in" , "r" , stdin ) ;
	freopen ( "rmq.out" , "w" , stdout ) ;

	scanf ( "%d", &N );
	int log2[N + 1];
	log2[1] = 0;
	for ( int i = 2; i != N + 1; ++i ) {
		log2[i] = log2[i >> 1] + 1;
	}

	for ( int i = 0; i != N; ++i ) {
		scanf ( "%d", &f[0][i] );
	}
	for ( int i = 1; i != log2[N] + 1; ++i ) {
		for ( int j = 0; j != N - ( 1 << i ) + 1; ++j ) {
			f[i][j] = max ( f[i - 1][j], f[i - 1][j + ( 1 << ( i - 1 ) )] );
		}
	}
	scanf ( "%d", &M );
	for ( int i = 0; i != M; ++i ) {
		int x, y;
		scanf ( "%d%d", &x, &y );
		--x;
		--y;
		if ( x == y ) {
			printf ( "%d\n", f[0][x] );
			continue;
		}
		int k = log2[y - x];
		printf ( "%d\n", max ( f[k][x], f[k][y - ( 1 << k ) + 1] ) );
	}
	return 0;
}
  评论这张
 
阅读(19)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018