资源描述：
《5_RMQ在信息学竞赛中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、RMQ在信息学竞赛中的应用RMQ在信息学竞赛中的应用中山纪念中学宋新波【摘要】RMQ在当今信息学竞赛的题目中经常被用到，本文主要讲解RMQ的原理和一些应用。【关键词】RMQ【正文】RMQ是英文RangeMaximum(Minimum)Query的缩写，顾名思义是用来求某个区间内的最大值或最小值，通常用在要多次询问一些区间的最值的问题中。RMQ的原理实际上是动态规划，我们用A[1..N]表示一组数，用[Li,Ri]表J示题目中所涉及到询问区间。设F[I,J]表示从A[I]到A[I+2−1]这个范围内的最JJ大值，也就是以A[I]为起点连
2、续2个数的最大值，由于元素个数为2个，所以J−1从中间平均分成两部分，每一部分的元素个数刚好为2个，如下图：J−1A[I]A[I+2]整个区间的最大值一定是左右两部分最大值的较大值，满足动态规划的最J−1优化原理，分析得到状态转移方程：F[I,J]=max(F[I,J-1],F[I+2,J-1])，边界条件为F[I,0]=A[I]，这样就可以在O(NlgN)的时间复杂度内预处理F数组。对于题目中所涉及到的询问[Li,Ri]来说，求出最大的X满足XXX2≤Ri−Li+1，那么区间[Li,Ri]=[Li,Li+2−1]∪[Ri+1-2,R
3、i]，如下图所示：第1页共5页RMQ在信息学竞赛中的应用X区间[Li,Li+2−1]X区间[Ri+1-2,Ri]X两个区间的元素个数都为2，所以[Li,Ri]的最大值为Xmax(F[Li,X],F[Ri+1-2,X])，可以在O(E)内计算出来。下面通过一个具体的例子来说明：题目：与众不同【题目描述】A是某公司的CEO，每个月都会有员工把公司的盈利数据送给A，A是个与众不同的怪人，A不注重盈利还是亏本，而是喜欢研究“完美序列”：连续的互不相同的序列。A想知道区间[L,R]之间最长的完美序列。【输入格式】第一行两个整数N，M(1<=N,
4、M<=200000)，N表示连续N个月,编号为06到N-1，M表示询问的次数。第二行N个整数(绝对值不超过10),第i个数表示该公司第i个月的盈利值。接下来M行每行两个整数L,R(0<=L<=R<=N-1),表示A询问的区间。【输出格式】输出M行，每行一个整数对应询问区间内的完美序列的最长长度。【样例输入】92254123624第2页共5页RMQ在信息学竞赛中的应用0826【样例输出】65【分析】用Last[value]表示数值value最近出现的位置，一开始全部赋为0，用ST[I]第i个数为结尾的最长完美序列的起始位置，ST的计算可
5、以用以下递推式得到ST[I]=MAX(ST[I-1],Last[A[I]]+1)，用F[I]表示第I个数为结尾的最长完美序列的长度，很显然F[I]=I-ST[I]+1，ST[I]和F[I]都可以在O(N)内计算出来。由ST的递推式可知，ST的值是一个非递减的序列，那么对于一个询问区间[Li,Ri]，该区间内的ST值可能会出现：左边一部分的ST值不在区间内即小于Li，而右边一部分的ST值大于等于Li,由于ST值具有单调性，所以这个分界点可以通过二分得到，假设该位置求出来为Mi,即ST[Li..Mi-1]=
6、Li，如下图所示：Mi那么整个区间[Li,Ri]的最长完美序列的长度，分为两部分来求，其中左边部分的最大值很显然为Mi-Li，而右边一部分由于ST值大于等于Li,所以就是求[Mi,Ri]内F的最大值，可以用RMQ的方法来求，所以整个问题的时间复杂度为O((M+N)*lgN)，分别是RMQ预处理的时间+询问二分的时间。【源程序如下】usesmath;constmaxn=200000;varn,m:longint;a,st,f:array[0..maxn]oflongint;第3页共5页RMQ在信息学竞赛中的应用last:array[-1
7、000000..1000000]oflongint;rmq:array[0..maxn,0..20]oflongint;procedureinit;vari:longint;beginreadln(n,m);fillchar(st,sizeof(st),0);fillchar(f,sizeof(f),0);f[0]:=1;fori:=1tondobeginread(a[i]);st[i]:=max(st[i-1],last[a[i]]+1);f[i]:=i-st[i]+1;last[a[i]]:=i;end;end;procedure
8、rmq_init;vari,j:longint;beginfori:=1tondormq[i,0]:=f[i];forj:=1totrunc(ln(n)/ln(2))dobeginfori:=1ton+1-(1shlj)
