cnblog 导航
看了眼 P5903 的题解区，方法还是挺多的，那我就浅浅的总结一下。
Algorithm 1
最简单的，直接往他的父亲节点跳，单次询问复杂度 \mathrm O(n)，总复杂度为 \mathrm O(qn)。这是最基础的写法。
Algorithm 2
我们用倍增的思想来做，这个也很简单不多讲，单次的复杂度为 \mathrm O(\log n)，总复杂度为 \mathrm O(q \log n)。
Algorithm 3
我们可以考虑使用重链剖分。如果这个链的顶端没有跳过的话，就直接跳到链顶的父亲，否则直接推就可以了，因为 dfs 序是连续的。单次复杂度也是 \mathrm O(\log n)，总复杂度为 \mathrm O(q \log n)。
看似复杂度是一样的，但是速度比 Algorithm 2 要快许多，此时已经可以通过了。
Algorithm 4
我们考虑如何优化 Algorithm 3。
我们发现我们需要跳到 k 级祖先的重链，然后我们就可以 \mathrm O(1) 知道祖先的位置了。然而跳链过程是 \mathrm O(\log n)，瓶颈就这这里。我们考虑如何更快地找到这条链。
我们发现一个点上面至多有 \log n 条链，那么我们直接二分这个点锁在的重链的位置即可。单次的复杂度为 \mathrm O(\log \log n)。由于瓶颈在前面了，所以总复杂度不变。
Algorithm 5
我们依然考虑如何优化 Algorithm 3。
我们可以一次跳 \sqrt{\log n} 个祖先，这样子我们就可以一次多跳几个祖先了。
单次复杂度为 \mathrm O(\sqrt{\log n})，总复杂度为 \mathrm O(q \sqrt{\log n})。
Algorithm 6
这题的正解：长链剖分。
比较麻烦。先按照节点深度树剖。然后利用倍增数组跳到 2^x，剩余的距离差为 k_1，这里 2^x > k_1。然后由于长链的长度 > k_1，那么因此可以先将 x 跳到 x 所在链的顶点。
若之后剩下的级数为正，则利用向上的数组求出答案，否则利用向下的数组求出答案。单次时间复杂度 \mathrm O(1)，但是瓶颈在前面，复杂度为 \mathrm O(n \log n)。
注意：以下内容非本题正解！！
Algorithm 7
这题还有一个比较科技的做法-----用 \pm 1 \ \text{FS(Find Smaller)} 解决 \text{LA} 问题。
我们发现 x 的深度为 d 的祖先是他后面的第一的深度 \le d 的节点。那么这个问题就是一个 \text{FS} 问题了。
然后欧拉序具有 \pm 1 的性质。那么这个问题就变成了 \pm 1 \ \text{FS(Find Smaller)} 问题，这个问题有良好的性质。可以支持在线常数查询。
定义：\text{ctz}(z) 表示 \max_{k = 0} 2^k \mid x。
定义：\text{lbt}(i,j) 表示 i 和 j 之间 \text{ctz} 最大的数。
引理：对于任意的 i,j，都有 j - i + 1 \le 2^{\text{lbt(i,j) + 1}}。
假设我们现在给出的数组为 a_{0,1,\cdots \cdots n - 1}。然后我们定义 f(i) = 3 \times 2^{\text{ctz(i)}},f(0) = n。然后我们定义 B_{i,1,2 \cdots f(i)}，其中 B_{i,j} = \text{Fz}(i,a_i - j)。
然后当我们查询 i 后面第一个大于 x 的数的位置时，答案如下：
-
若 a_i \le x，答案为 i。
-
否则
- 令 d = a_i - x，若 d \le f(i)，那么答案为 B_{i,d}。
- 否则，我们令 d = lbt(i - d + 1,i)，那么答案为 B_{k,a_k - x}。
那么问题就变成了如何在 \mathrm O(n \log n) 预处理出 B 数组。当然处理是简单的，我们只需要倒着扫一遍，然后用一个桶记录一个数最前的出现位置。然后最终的复杂度就是 O(n \log n)。
Algorithm 8
最高贵的线性做法！！！！！是 Algorithm 7 的进阶版本，在 Algorithm 7 当中定义的所有东西都在这里适用。
我们先定义 \text{Fs}(i,x) 为 i 后面第一个 \le x 的数的位置。
考虑分块，我们取 b = \lfloor \frac{\log n}{2} \rfloor。然后我们先考虑块间的贡献。
对于每一个块，我们维护一下两个信息：
注意到如果 F_{i,j} = k，那么 a_{ib} - jb \le a_{kb} < a_{ib} - (j - 1)b。这个式子可以用 \pm 1 性质证明。
然后我们考虑如何查询 \text{Fs}(ib + j,x)。
- 若 x \ge a_{ib + j} 返回 ib + j。
- 若 j > 0：
- 通过块内查询，若答案在块内，则直接返回；
- 若答案不在块内，那么返回 \text{Fs}((i + 1)b,x)；
-
- 若 $x \ge a_{ib} - jb$，返回 $N_{i,a_{ib} - x}$；
- 令 $d = \lfloor \frac{a_{ib} - x}{b} \rfloor$：
- 若 $d \le f(i)$，那么返回 $\text{Fs}(F_{i,d}b,x)$；
- 否则返回 $\text{Fs}(\text{lbt}(i - d + 1,i)b,x)$。
然后我们发现因为：
a_{kb} < a_{ib} - (d - 1)b < x + 2b
所以所有的情况，都会变成 j = 0 的第一种情况。
然后我们考虑块内怎么做。
接下来是利用位掩码的方法，一般块长取 w。
m(i,j)=\begin{cases}1\\ \ \ \ \ a_j < \min\{a_i,\dots,a_{j-1}\}\\0\\ \ \ \ \ mathrm{otherwise}.\end{cases}
那么，m(ib+j,ib+j+1),m(ib+j,ib+j+2)\dots m(ib+j,ib+(b-1)) 中第 a_{ib+j}-x 个 1 的位置就对应 \mathrm{Fs}(ib+j,x)，如果不存在这样的位置，则说明答案不在块内。
我们将 m(ib+j,ib+j+1),m(ib+j,ib+j+2)\dots m(ib+j,ib+(b-1)) 压入一个数 m_{ib+j} 内，查询即为查找第 k 个为 1 的二进制位位置，这一操作可以进行一些预处理后 O(1) 实现。
那么我们就获得了 \mathrm O(n) - O(1) 的写法了。