poj3264:Balanced Lineup【RMQ模版+总结】
咳咳,好久没有写题解了。虽说是退役了,但高三的最后一届NOIP还是要好好参加的,所以说这段时间也不会去弄特别复杂的东西。
这段时间在扫清一些NOIP知识点,发现有个叫做RMQ和LCA的东西还没有学。仔细搜索记忆后好像在初中讲过但是当时没有弄明白,一直拖到了现在。
RMQ就是传说中的区间最值查询,虽然说这东西是线段树的一个基本功能,但是线段树这个东西嘛,常数是一个很大的问题,所以了解一下RMQ的其他算法也是很不错的。
RMQ可以用离线的ST算法,嗯离线算法嘛,就是先预处理出一大堆东西,然后再用很快的时间回答各个问题。
ST算法的时间复杂度是O(NlogN),嗯跟线段树的时间差不多是吧~
那个log是用了倍增的思想,我们可以:
f[i,j]表示序列A中从第i位开始,连续2^j位的子序列中的最大/最小值。
我们可以发现,i的范围是1~N,j的范围是1~log2N,然后我们可以用以下的方法来巧妙递推出整个f数组:
首先假设我们已经推出了j=1~k时候的f数组,那么f[i,k+1]对应的序列可以拆成两个长度位2^k长度的序列,所以说:
f[i,k+1]=max/min(f[i,k],f[i+2^k,k])
所以只要按照j的递增顺序就可以递推出这个表。
而查询时也会遇到问题:我们的f数组只处理出了一部分序列,所以不可能只用f数组的某一个值查询出结果,但是可以这么想:
查询(l,r)区间,可以把(l,r)分成两个尽量大的、长度为2^k的序列,当然因为(l,r)序列长度是任意值,所以说两个序列需要有一定的重叠,反正重叠部分计算最值是不会对答案有影响的,所以说:
max/min(l,r)=max/min(f[l,k],f[r-2^k+1,k])
其中k=log2(r-l+1)
那么这样就算解决了RMQ问题。
了解了RMQ的处理方法,可以来一道例题,就是本文标题的这个:
题目大意:FJ有N头牛,每头牛有一个高度ai,然后有M个询问,每次问区间(l,r)中高度最高的牛和高度最低的牛高度的差。
好吧如果你看懂了上面的东西,这题应该就会了。
代码:
var a:array[1..50000]of longint; b:array[0..20]of longint; minn,maxx:array[1..200000,0..20]of longint; n,m,i,j,k,l,p,q:longint; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; begin read(n,m); for i:=1 to n do read(a[i]); b[0]:=1; while b[l]<n do begin inc(l); b[l]:=b[l-1] shl 1; end; fillchar(minn,sizeof(minn),127); for i:=1 to n do begin minn[i,0]:=a[i]; maxx[i,0]:=a[i]; end; for i:=1 to l do for j:=1 to n do begin minn[j,i]:=min(minn[j,i-1],minn[j+b[i-1],i-1]); maxx[j,i]:=max(maxx[j,i-1],maxx[j+b[i-1],i-1]); end; for i:=1 to m do begin read(p,q); l:=trunc(ln(q-p+1)/ln(2)); writeln(max(maxx[p,l],maxx[q-b[l]+1,l])-min(minn[p,l],minn[q-b[l]+1,l])); end; end.
发表评论