st, LCA

NOIP

Sparse Table算法

$Sparse Table$算法，简称ST算法，可以用来求解RMQ（区间最值查询）问题。
RMQ问题的形式一般是：存在一个大数组，要求对于给定的起点和终点，迅速回答出这段区间的最大值或最小值。
朴素的方式是扫描起点到终点的所有数，维护其中的最值，这样的复杂度是$O(n^2)$的，速度太慢。ST算法是使用的是类似于二分的动态规划思想，其复杂度是$O(nlogn)$，因此查询速度非常快。
ST算法的执行过程（以求最大值为例）：

1、初始化：

设原数组为x[N]。
开辟一个数组dp[N][33]。其中dp[i][j]表示的是从下标为i的元素开始，到下标为$(i + 2^j - 1)$的元素为止，这些元素中的最大值。对于整型而言，其值不会超过$2^32$，因此第二维大小为33已经足够。
因此dp[i][0]表示的是元素本身，因此可以初始化为dp[i][0] = x[i]。
对于其他的dp[i][j]，可以采用动态规划的方式求出，递推式为dp[i][j] = max(dp[i][j - 1], dp[i + 2 ^ (j - 1)][j - 1])，其实就是把一段区间切成两段大小相等的区间，当前区间的最大值就是两个子区间的最大值中的较大者。
初始化的复杂度为$O(nlogn)$。

2、求解：

对于给定的起点$beg$及终点$end$，可以得出区间大小为$range = end - beg + 1$。
因此可以找到一个整数k = (int)(log(range) / log2)。这样区间就可以被划分为子区间1，即$[beg, beg + (2 ^ k) - 1]$，子区间2，即$[end - (2 ^ k) + 1, end]$。 这两个可能会有重叠，但重叠不会影响最大值的求解。因此对于$beg$和$end$，可以得到解为$res = max(dp[beg][k], dp[end - (2 ^ k) + 1][k])$。
求解的复杂度为$O(1)$。
值得注意的是使用$log$求解$k$的速度比较慢，可以使用乘法来计算k，这样速度会相对快一些。
具体方法是：

k = 0, x = 2, range = end - beg + 1;
while (x <= range){
    k++;
    x <<= 1;
} 

对于某个RMQ问题，总的复杂度为 $O(nlogn) + n * O(1) = O(nlogn)$， 因此可以在足够快的时间内得到区间的最大值或最小值。

Balanced Lineuppoj3264

题意：给出n头牛的高度，问区间[x ，y]中最高值与最低值的差

A Magic Lamp

题意：

对于一个序列A[1...N]，一共N个数，除去M个数使剩下的数组成的整数最小。
也就是说在A[1...N]中顺次选取N-M个数，使值最小。

Sample Input

178543 4
1000001 1
100001 2
12345 2
54321 2

Sample Output

13
1
0
123
321

随便讲讲

它主要是基于以下事实：

对于序列$A[1...N]$，选取$N-M$个数，使组成的值最小，而且顺序不能交换，既然要选取$N-M$个，那么可以容易知道这$N-M$位数的第一位一定在数组$A$中的区间$[1，M+1]$中出现，

为什么是这样呢？

我们可以这样来模拟一下：假设A数组就只有6个数，分别是$A[1]，A[2]，A[3]，A[4]，A[5]，A[6]$，我们去掉$M=2$个数，使形成的值最小。

那么我们此时的$N=6,M=2，N-M=4$

则我们说形成的4位数的第一位一定在区间$[1，3]$中出现，因为如果区间范围再大点，比如$[1，4]$，这样就不科学了，因为第一位一定不会是$A[4]$，更不会是$A[5]，A[6]$，我们假设可以是$A[4]$，那么后面只有$A[5]，A[6]$两位数了，这样的话最多只可能形成3位数，绝对不能形成$N-M=4$位了。

当然到了这里，我们就可以这样做了，第一位可以在区间$[1，M+1]$里面找，假设第一位在位置x，因为第二位肯定在第一位的后面，所以第二位一定存在于区间$[x+1，M+2]$，为什么是$M+2$,因为第一位已经确定了，现在只需要确定$N-M-1$位了，所以区间就可以向后增加1，一直这样循环下去，就可以找到了。

Cornfields 二维

给你一个$n*n$的矩阵，让你从中圈定一个小矩阵，其大小为$b*b$，有$Q$个询问，每次询问告诉你小矩阵的左上角，求小矩阵内的最大值和最小值的差。

思路：

1、一维RMQ可以用来求线性区间最大值问题。那么我们不如将一维变成二维，将maxn[][]变成maxn[i][j][len]表示在第i行中，以[j，j+len-1]区间内的最大值。

2、然后我们求$N^2LogN$预处理这个问题。然后$O（n）$来查询区间最大值和最小的值的差即可。

区间gcd

题目大概说给一个包含$n$个数的序列，多次询问有多少个区间$GCD$值等于某个区间的$gcd$值。

$n = 1e5, q = 1e5$

emmmmm

讲解：

任何一个区间不同的GCD个数是log级别的，因为随着右端点向右延伸GCD是单调不增的，而每次递减GCD至少除以2。

考虑固定左端点，最多就$nlogn$种GCD，可以直接把所有区间GCD值预处理出来，用map存储各种GCD值的个数，查询时直接输出。

具体是这样处理的：枚举左端点，进行若干次二分查找，看当前GCD值最多能延伸到哪儿，进而统计当前GCD值的数量。

而求区间GCD，用ST表，预处理一下，就能在$O(1)$时间复杂度求出任意区间的gcd了。

线性结构拓展到树上，LCA

货车运输 2013年NOIP全国联赛提高组

codevs3287

题目描述 Description

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入描述 Input Description

第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。

输出描述 Output Description

输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。

样例输入 Sample Input

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

样例输出 Sample Output

3
-1
3

数据范围及提示 Data Size & Hint

对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q < 1,000；
对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q < 1,000；
对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q < 30,000，0 ≤ z ≤ 100,000。