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

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

RMQ算法  

2015-12-03 13:06:36|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

       RMQ,很奇怪的名字,可其中却蕴藏着我们梦寐以求的东西——区间求最值!

        假设有这样一个题目,就是有n个数,有m次讯问,每次输入两个整数,st,表示从数组的第s位开始,到数组的第t位的最大值,0<n,m<=1000000<s<=t<=100000

=============================开始分析============================

例如有7个数:

 3 2 5 4 1 7 3

        我们看一看,一定会发现,个数和询问次数都很大。要是普通的做法,O(n+m*(t-s)),是会超时的。现在,我们就用RMQ

        RMQ,就是用O(nlog2n)的预处理,就可以用O(1)的速度求出区间的最值。不过空间很大,是nlog2n的。

设状态f[i][j]为从数组第j位开始,到j+(1<<i)-1位的最大值。i最大为log2n

                                    RMQ算法 - 杨鸿飞 - 一个叫杨鸿飞的人的博客

 
       这样子的话,通过预处理,求i~j的距离,就可以O(1)的时间求出最大值了。如图:

=============================先给个程序===========================

#include <iostream>

 

using namespace std;

 

int N,a[100100];

int f[20][100100];

int lo[100100];

 

void YCL_log()

{

 lo[1]=0;

 for (int i=2; i<=N; i++) lo[i]=lo[i/2]+1;

}

 

int qmax(int le,int ri)

{

 int t=lo[ri-le+1];

 if (t==0) return a[le];

 return max(f[t][le],f[t][ri-t+1]);

}

 

void YCL_RMQ()

{

 for (int i=1; i<=lo[N]; i++)

   {

     int t=1<<(i-1);

      for (int j=0; j<N-t+1; j++)

      f[i][j]=qmax(j,j+t-1);

    }

}

 

 

int main()

{

 cin>>N;

 for (int i=0; i<N; i++) cin>>a[i];

 YCL_log();

 YCL_RMQ();

 int m;

 cin>>m;

 for (int i=0; i<m; i++)

 {

  int l,r;

  cin>>l>>r;

  cout<<qmax(l-1,r-1)<<endl;

 }

 return 0;

  评论这张
 
阅读(17)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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