2026夏从0开始的倍增讲解

· · 算法·理论

热身小练：如何用尽可能少的砝码称量出 [0,31] 之间的所有重量？（只能在天平的一端放砝码）

答案是使用 1 2 4 8 16 这五个砝码。

如何证明？假如我们现在的砝码能够称量出 1-S 那么我们下一次选 S+1 一定是最优的。

什么是倍增？顾名思义，即是成倍增长。从上一个例题来看，因为一个数总是关于 k 的次幂具有可划分性，通常 k=2 ，也就是每一个数都可以被二进制拆分，表示成若干个 2 的次幂项的和的形式。

因此面对一个数时，我们只需要枚举 k^i 中的 i ，而不需要一个一个的把这个数数出来。这样时间就从 O(n) 降到了 O( \log_{}{n} ) 。

经常被用于 st 表和 lca 算法。（一会儿会讲）

快速幂

因为指数非常大，对 b 进行枚举是不行的。

注意到，b 可以被拆成若干个 2 的次幂项的和的形式。

也就是 a^b = a^{\sum\limits_{i=1}^n (0/1) \times 2^i} 且指数最终等于 b。

即 a^b = (0/1) \times a \times (0/1) \times a^{2} \times (0/1) \times a^{2^2} \times (0/1) \times a^{2^3} \times ....

这样拆分的话，2 的幂次最大为 O( \log_{}{b} ) ，这一系列东西可以通过 a 的自乘来得到。

这样 O( \log_{}{b} ) 就做完了。

ST 表 & RMQ 问题

考虑暴力，复杂度 O(N \times M) 肯定过不了，不难猜到目标应该是 O(N \times \log_{}{}) 的。

考虑预处理呢？不同的区间一共有 N^2 个啊更搞不了了。

其实并不需要预处理所有的区间，该以什么方式预处理又不超时又有效呢。

根据之前的提示，还是得从 2 的次幂下手。

可以发现，对于每一个查询的区间 (l,r) ，区间内的 \max 总可以由以 l 为起点的一个长度为 2^? 的区间 \max 与以 r 为右起点长度为 2^? 的区间 \max 相拼起来，并且这样是不会漏的。

而这个东西不禁让我们联想到之前的 2 的次幂拆分可以被运用到预处理上。

具体的，我们记 st_{i,j} 表示，以第 j 位为开头，长度为 2^i 的这个区间的 \max 是多少。

初始化为 st_{0,j}=a_j ，转移为 st_{i,j}=max(st_{i-1,j},st_{i-1,j+(1<<(i-1))})

顺理成章地，查询答案即为：

假设 t=\log_{2}{r-l+1} ，则 ans = \max(st_{t,l},st_{t,r-(1<<t)+1})

st 表可以被用于满足结合律（调换计算顺序不影响），不带修改，可重复贡献的问题。可以 O(n\times \log_{}{n}) 预处理，并在 O(1) 完成区间查询。

最近公共祖先（LCA）

考虑暴力。

这可以分为两步，先使得两个点在树中跳到同一深度，再同时向上跳直到跳到两点跳到一起——即为两人的 lca。

不难发现这是可以用上述的同样方法进行优化的。

对于第一部分，可以发现假如说两个点的深度差为 k ，同样的，我们可以对 k 进行二进制拆分，并预处理 st_{i,j} 表示当前为节点 j ，向上走 2^i 步的位置是哪里。

初始化 st_{0,j}=fa_j ，转移是 st_{i,j}=st_{i-1,st_{i-1,j}}。

这样我们便可以在 O(\log_{}{dis}) 将两个点搞到同一高度。

对于第二部分也不难搞，预处理可以继续用。

注意到一个性质，两点的 lca 的祖先们一定是两个点的公共祖先，并且现在两个点是同步的。

因此具有单调性，考虑二分？

但你经过一些思考就会发现，这样复杂度是平方的，但这并不需要。

可以发现，其实我们只需要倍增就可以了。

具体的，我们再把这个过程分为两部分。1.尽可能往上跳，但不跳到 lca ，也就等价于最终跳到了 lca 中的一个儿子。

接着，跳最后一步，找到 lca。

这样我们就可以在合理复杂度内完成了。

策略游戏

理解一下，什么是两人的最优策略？

注意两人是先后手操作的。

假设 A 先选了一个数， B 必然会取其中对自己最有利，对 A 最不利的数。

那么 A 也就是需要使得自己选出的数，与 B 的那些数相乘的最小值最大。

仔细考虑一下，其实整个问题的关键是正负数的处理。

具体的，假如 A 选择了一个正数，那么如果 B 有负数或 0 则必然会选最小的负数。

因此对于这种情况， A 便会选择最小的正数。

关键区别就在于 B 到底是不是全正的。

我们发现对于一个人有 3 种不同的情况 ： 全正，全小于等于 0 ，都有。

组合起来就一共有 9 种不同的分讨，但这并不困难，可以举几个例子自己就应该会推了。

经过一些讨论可以发现我们需要维护的是 : A 的最大数，A 的最小数，A 的最小正数 ，A 的最大负数 ， B 的最大数 ， B 的最小数。

可以发现我们需要对这个东西进行预处理，也就是开 6 个 st 表求最值。

时间复杂度 O(n\times\log_{}{n})。

大量的工作沟通

非常模板的一道题。

转化一下，这些主持应满足什么条件。

很明显的，它应该是给出所有点的公共祖先。

应该怎么找呢？

不难发现，这些点应该是他们 lca 到根节点路径上的点们。

至于整体 lca 是可以通过 M 次求两两 lca 做完的。

具体的，现用 A 和 B 求出 lca1，再用 lca1 与 C 求出 lca2，以此类推即可，不难发现这是对的。

接下来因为题目要求找到编号最大的，所以需要从这个 lca 到根再找一遍即可，当然预处理前缀最大值也没问题。

复杂度 O(Q \times ( M \times\log_{}{n}+n)) 或 O(Q \times ( M \times\log_{}{n}))

ZAB-Frog

首先考虑如何得出每个点的第一步是哪里。

我们需要一个 O(\log_{}{n}) 的做法，可以考虑二分。

注意到单侧点的距离是有单调性的，并且 nxt 可能出现在答案的两侧，因此我们考虑对两侧分别做二分答案。

找出离 i 最近的使的这个点的距离大于等于对面那个点的距离的位置，如果它还小于等于对侧点的下一个点，那么便可能成为答案。

如果左右都存在就选左边（题目要求）。

但是 m 非常大，一步一步跳会超时。

与之前同理，我们可以对 m 进行二进制拆分。

具体的，我们计 st_{i,j} 表示从编号为 j 的石头跳 2^i 步会到哪里。

这样对于每个点可以在 \log_{}{m} 内跳到终点。

加起来时间是 O(n \times \log_{}{m}) 的。

是说的对但是。

考虑压维，发现 m 是固定的，所以可以在递推过程中做答案的统计，不需要保留第一维。

转移需要做一个类似 dp 的滚动数组。

这样空间只用 n 就搞完了。

国旗计划

首先可以先把题目简化一点，因为是一个环，所以起点在哪里都可以，因此 j 的要求可以等价于要求从 j 出发。

环上不好考虑，考虑断环成链。

结合没有区间相包含这一性质，提示我们每一个人的最优接棒人是谁？

因为要求人数最少，所以最优指的是向外跑的最远的人，注意到这个人会是区间内的最后一个人。

这个人应当怎么求？

可以先把人按左端点排序，对每一个人进行二分找接棒人 O(n\times\log_{}{n}) ，也可以通过一个双指针做到 O(n)。 （ 虽然排序已经 O(n\times\log_{}{n}) 了 ）

因此基于这个贪心我们有了一个 O(n^2) 的暴力，即为对每个人都暴力一步一步跳直到跳完整个圈。

该如何把复杂度降到单人 \log_{}{} 呢？

依旧照葫芦画瓢，像 lca 的第二步跳一样。预处理 st_{i,j} 表示当前在第 j 个人，一共经过 2^i 个人后下一个接棒人会是谁。

初始化 st_{0,j}=nxt_j ，转移同理。

查询跟 lca 一样，分为跳到自己之前和跳到自己两部分，二进制下从高位向低位枚举，如果跳这一次跳不过，就跳，最后累加答案并加 1 就完成了。

--- [Math Homework](https://www.luogu.com.cn/problem/P9027) 注意到 $z \le 16$ 。 我们可以把整个问题分成两部分：1.构造 2.检查。 构造出什么东西呢？我们可以构造出一个 $a_i$ 满足 $a_i$ 等于这个位置上所有被要求的 $z$ 的 $\operatorname{lcm}$，这样它已经做到了它的最好，如果在 check 时大于要求的 $z$ 也是无奈之举，只能是 impossible因为我们不能对于任何数删掉任何的因数了，因为这样必然会使一条限制是小于 $z$ 的。 但如果每来一条限制都认真完成肯定是超时的。 因为 $z$ 很小，我们可以考虑差分后前缀和完成这些区间加操作，具体的，计 $sum_{i,j}$ 表示在位置 i 上， $z$ 等于 j 的操作共执行了多少次，最终如果一个位置不是 1 ，则为真。 这样可以 $O(n\times z)$ 完成第一部分。 第二部分便非常简单了，暴力显然不行，不难想到 st 表维护区间 $\gcd$ 之后就跟板子一模一样了。 没错因为 1-16 的 $\operatorname{lcm}$ 是 720720 所以限制 1 只是不让你瞎搞。 --- [CCDSSQ](https://www.luogu.com.cn/problem/CF475D) 考虑一些暴力。对了区间 $\gcd$ 默认已经用 st 预处理好，可以 $O(1)$ 取用。 考虑认真的对待每一个询问，我们能做枚举 $l$ ，之后二分找到第一个成立和第一个失败的位置，相减就是答案。 $O(q \times n \times \log_{}{n})$ 复杂度在玩火。 我们似乎太认真了，考虑预处理答案并 $O(1)$ 回答。 啊啊？ $x$ 不是 $10^9$ 吗？不难发现很多都是 0 ，有用的只有最多只有 $n \times\log_{}{v}$ 的，这是因为可以发现 $\gcd$ 的一个性质：在我们固定起点并向右扩展的过程中，每一次变化至少会使这个 $\gcd$ 除 2。因此最多 $\log$ 次就会成 1。 我们同样可以每次二分找到下一个位置，这样 $O(n \times \log_{}{V} \times \log_{}{n})$ 做完预处理，并且肯定跑不满。 --- [MEX of lcm](https://www.luogu.com.cn/problem/CF1834E) 法一： ~~我真不行了这不跟上题是双倍经验吗，很难想象我在做过一遍后模拟赛还做不出来我错了扯远了。~~ 注意到答案必定小于前 n+1 小的质数的最大值，大概 $4\times 10^6$。 并且 $\operatorname{lcm}$ 也具有每变一次乘 2 的性质，同样二分加 st 表组合拳，$\operatorname{lcm}$ 大于 $4\times 10^6$ 就 break 复杂度 $O(n\times \log_{}{v} \log_{}{n} + v)$ 同样跑不满。 法二 by hzr: 简直是天才，但他赛时也不知道能过。 仍需要：注意到答案必定小于前 n+1 小的质数的最大值，大概 $4\times 10^6$。 对于每一个 l 我们还是向右扫，但是每当当前 $\operatorname{lcm}$ 是 $a_{l-1}$ 的倍数时便 break 这并不难理解。因为如果是这样之后的每一步都当 l-1 作为 l 时统计过。 正确性是毋庸置疑的，但时间复杂度为什么是对的呢。 注意到，在我们这么做操作是， $(l,r)$ 的 $\operatorname{lcm}$ 小于 $(l-1,r)$ 的 $\operatorname{lcm}$ ，因此我们把主观视角切到 r ，每个 r 的合法的 l 只有 $\log_{}{V}$ 个，因此总复杂度为 $ O(n\times (\log_{}{v})^2)$。 --- [Contests](https://www.luogu.com.cn/problem/P9361) 注意到 $m \le 5$。 考虑暴力，可以让每个点向比自己低的人连边之后每次询问进行 bfs 最短路， $O(Q \times m\times n^2)$ 差得有点远。 注意到答案小于等于 $n$。 考虑一些贪心。我们最终的目的形如，经过一些跳跃后在第 $i$ 行我们跳到了 $y$ 的前面。因此我们可以考虑当我们确定一次跳跃要跳到某一行后最优该如何跳。 令当前在第 $i$ 行，我是 $x$ ，我能选的人有这场比赛中排名比我靠后的人们和我自己，根据贪心，我们需要找出这些人中在目标场次排名最靠前的人跳过去。 发现暴力找是 $O(m\times n^2)$ 的，但是注意如果我们对每场比赛都将排名从差向好枚举，我们要做的就是取一个前缀 min ，那这个东西一第推肯定 $O(m\times n)$ 即可。 现在我们已经有了每个人的第一步。现在可以考虑对于每个询问有什么更好的暴力。 因为最终的答案可能出现在任何一排，所以我们需要同时维护每一行最优能跳到哪里，初始化肯定是 $x$ 的每个分身处于每行的位置。 每一步，每个最优都可以考虑其他每一行作为下一步的终点并刷新那行的最优位置，我们可以重复做这个操作直到有一行成功。因为答案小于等于 $n$ ，所以至多拓展 $n$ 次，复杂度 $O(Q \times m \times n)$。 考虑如何将 $n$ 降到 $\log$。 依旧 st 表加倍增跳，定义 $st_{i,j,k}$ 表示，换了**小于等于** $2^i$ 个人，起始为名叫 $j$ 的人，最终要跳到 $k$ 行的最靠前排名是多少。 初始化就是每人的第一步。 转移 $st_{i,j,k}=min(st_{i,j,k},st_{i-1,a_{p,st_{i-1,j,p}},k})$ ，其中 $p$ 为中转的行在哪。复杂度为 $O( \log_{}{n} \times n \times m^2)$。 对于查询，考虑 lca 同样的跳，$O(Q \times \log_{}{n} \times m)$。 注意，输出是求出答案的 $+2$ ，因为这个跳的步数是不包含第一步的，并且我跳到的位置需要先跳到那个小于 $y$ 的位置再跳到 $y$ 所以要 $+2$。 还需要注意，如果答案是 1 ，也就是在一行内 $x$ 就比 $y$ 高需要特判。 结束了！