From faa2b66a61a1d64d5cce8042a5fb1c8d80a752d3 Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Wed, 30 Sep 2020 05:02:13 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/basic/binary-lifting.md | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) diff --git a/docs/basic/binary-lifting.md b/docs/basic/binary-lifting.md index 67d11f11..27092061 100644 --- a/docs/basic/binary-lifting.md +++ b/docs/basic/binary-lifting.md @@ -6,21 +6,21 @@ author: Ir1d, ShadowsEpic, Fomalhauthmj, siger-young, MingqiHuang, Xeonacid, hsf 倍增法（英语：binary lifting），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。 -这个方法在很多算法中均有应用，其中最常用的是 RMQ 问题和求 [LCA（最近公共祖先）](../graph/lca.md)。 +这个方法在很多算法中均有应用，其中最常用的是 RMQ 问题和求 [LCA（最近公共祖先）](../graph/lca.md) 。 ## RMQ 问题 -参见：[RMQ 专题](../topic/rmq.md) +参见： [RMQ 专题](../topic/rmq.md) -RMQ 是 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。使用倍增思想解决 RMQ 问题的方法是 [ST 表](../ds/sparse-table.md)。 +RMQ 是 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。使用倍增思想解决 RMQ 问题的方法是 [ST 表](../ds/sparse-table.md) 。 ## 树上倍增求 LCA -参见： [最近公共祖先](../graph/lca.md/#_5) +参见： [最近公共祖先](../graph/lca.md/#_5) ## 例题 -### 题1 +### 题 1 ???+note "例题" 如何用尽可能少的砝码称量出 $[0,31]$ 之间的所有重量？（只能在天平的一端放砝码） @@ -30,7 +30,7 @@ RMQ 是 Range Maximum/Minimum Query 的缩写，表示区间最大（最小） 为什么说是极少呢？因为如果我们要量出 $[0,1023]$ 之间的所有重量，只需要 9 个砝码，需要量出 $[0,1048575]$ 之间的所有重量，只需要 19 个。如果我们的目标重量翻倍，砝码个数只需要增加 1。这叫“对数级”的增长速度，因为砝码的所需个数与目标重量的范围的对数成正比。 -### 题2 +### 题 2 ???+note "例题" 给出一个长度为 $n$ 的环和一个常数 $k$ ，每次会从第 $i$ 个点跳到第 $(i+k)\bmod n+1$ 个点，总共跳了 $m$ 次。每个点都有一个权值，记为 $a_i$ ，求 $m$ 次跳跃的起点的权值之和对 $10^9+7$ 取模的结果。 @@ -40,17 +40,17 @@ RMQ 是 Range Maximum/Minimum Query 的缩写，表示区间最大（最小） ??? note "解题思路" 这里显然不能暴力模拟跳 $m$ 次。因为 $m$ 最大可到 $10^{18}$ 级别，如果暴力模拟的话，时间承受不住。 - + 所以就需要进行一些预处理，提前整合一些信息，以便于在查询的时候更快得出结果。如果记录下来每一个可能的跳跃次数的结果的话，不论是时间还是空间都难以承受。 - + 那么应该如何预处理呢？看看第一道例题。有思路了吗？ - + 回到本题。我们要预处理一些信息，然后用预处理的信息尽量快的整合出答案。同时预处理的信息也不能太多。所以可以预处理出以 2 的整次幂为单位的信息，这样的话在预处理的时候只需要处理少量信息，在整合的时候也不需要大费周章。 - + 在这题上，就是我们预处理出从每个点开始跳 1、2、4、8 等等步之后的结果（所处点和点权和），然后如果要跳 13 步，只需要跳 1+4+8 步就好了。也就是说先在起始点跳 1 步，然后再在跳了之后的终点跳 4 步，再接着跳 8 步，同时统计一下预先处理好的点权和，就可以知道跳 13 步的点权和了。 - + 对于每一个点开始的 $2^i$ 步，记录一个 `go[i][x]` 表示第 $x$ 个点跳 $2^i$ 步之后的终点，而 `sum[i][x]` 表示第 $x$ 个点跳 $2^i$ 步之后能获得的点权和。预处理的时候，开两重循环，对于跳 $2^i$ 步的信息，我们可以看作是先跳了 $2^{i-1}$ 步，再跳 $2^{i-1}$ 步，因为显然有 $2^{i-1}+2^{i-1}=2^i$ 。即我们有 `sum[i][x] = sum[i-1][x]+sum[i-1][go[i-1][x]]` ，且 `go[i][x] = go[i-1][go[i-1][x]]` 。 - + 当然还有一些实现细节需要注意。为了保证统计的时候不重不漏，我们一般预处理出“左闭右开”的点权和。亦即，对于跳 1 步的情况，我们只记录该点的点权和；对于跳 2 步的情况，我们只记录该点及其下一个点的点权和。相当于总是不将终点的点权和计入 sum。这样在预处理的时候，只需要将两部分的点权和直接相加就可以了，不需要担心第一段的终点和第二段的起点会被重复计算。 这题的 $m\leq 10^{18}$ ，虽然看似恐怖，但是实际上只需要预处理出 $65$ 以内的 $i$ ，就可以轻松解决，比起暴力枚举快了很多。用行话讲，这个做法的 [时间复杂度](../misc/complexity.md) 是预处理 $\Theta(n\log m)$ ，查询每次 $\Theta(\log m)$ 。 -- 2.11.0