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.

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据