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.
发表评论