视频讲解——全球总决赛选手带你半小时玩转“线性倍增”

引入

分析

代码语言：javascript复制

void init()
{
 for (int i=1;i<=n;i  )
  f[i][0]=a[i];
 for (int i=1;(1<<i)<=n;i  )
  for (int j=1;j (1<<i)-1<=n;j  )
   f[j][i]=min(f[j][i-1],f[j (1<<(i-1))][i-1]);
}

考虑如何获取区间最小值。

我们可以通过从头查询一段超过一半的 2 的幂次的信息和从结尾开始的查询一段超过一半的 2 的幂次的信息，并且合并这两部分信息。

所以 RMQ 能够查询的问题一定是能够重复询问一段区间信息的问题。

代码语言：javascript复制

int query(int l,int r)
{
 int k=(int)(log(double(r-l 1))/log((double)2));
 return min(f[l][k],f[r-(1<<k) 1][k]);
}

可以发现，除了 Max/Min ，GCD 也满足 RMQ 查询的性质。

例题1

Codeforces359D Pair of Numbers

http://codeforces.com/contest/359/problem/D

分析

区间内有一个数可以被其他所有数整除，也就是满足

min _{i=l}^r a_i=gcd _{i=l}^r a_i

我们知道 GCD 会因为不断加入数变小。如果我们确定了左端点，右端点满足二分的性质。

所以我们可以枚举区间的最小值在什么位置，二分找到满足要求的最左边的左端点和最右边的右端点。

例题2

NOIP2012 开车旅行

https://loj.ac/p/2604

分析

首先要知道 A, B 从每个城市出发选择的目的地：对于一个城市，考虑它与它东面的所有城市的海拔高度，离它最近的城市一定是它排序以后的前驱或者后继。如果是前驱，则离它第二近的城市一定是它前驱的前驱或者它的后继；如果是后继，则离它第二近的城市一定是它后继的后继或者它的前驱。我们可以正着做，直接用 set 来维护。

怎么知道何时停止呢？我们可以从二进制高位向低位确定！

海外加速 http

0 人点赞