二进制优化：倍增法学习笔记
ZhangChuan1350
·
2026-05-14 22:15:04
·
算法·理论
前言
看洛谷没啥倍增好文于是写了这篇笔记
倍增法（思想），虽然在《NOI 大纲（2025 版）》只能算个入门级基础算法 的考点，基础思想简单易懂，却在各种题目不断变种，引申出多种算法，如提高组的 ST 表、最近公共祖先等。
本文将专注于倍增法的思想 ，因为只有深刻透彻思想，才能将倍增思想熟练运用在变种题中。而我翻遍洛谷算法·理论 专栏，仅发现这篇讲解倍增法的文章，似乎是面向初学者的，但内容不够详尽，于是我按照自己的学习成果，给倍增法写下这篇学习笔记 ，希望能帮到初学倍增的 OIer。
本文主要展示思路。
阅读建议 ：
假设我们要走 n 步，一步一步地走太慢，时间复杂度为 O(n) 。(n)_2 来走，因为 (n)_2 至多有 \lfloor\log_2n\rfloor+1 位数字，就只需 \lfloor\log_2n\rfloor+1 步就能走完，时间复杂度为 O(\log_2 n) 。
而 (n)_2 的每一位的权重可以视作为 k 。因此，每一次的倍增就是要求 2^k 的值。
> **为什么可以用二进制？**
> 先取特殊值 $n=13$，由于 $(13)_{10}=(1101)_2$，因此走 $13$ 步相当于走 $2^3+2^2+2^0$ 步。以此类推，倍增就只需要 $O(\log_2n)$ 的时间就能完成计算。
> **为什么不用其他进制？**
> 我们举三进制的例子。这次定 $n=16$，而 $(16)_{10}=(121)_3$，相当于走 $3^0+2\times3^1+3^2$ 步，虽然时间复杂度降到了 $O(\log_3n)$，但需要记录每一次倍增走多少步，较为麻烦，而二进制只需记录每一次倍增**有没有走**即可。
> 综上，其他进制做法既不是不行，而是**不够优雅**。二进制既平衡了效率 $O(\log_2n)$，又让编码变得更为容易。因此二进制做法是倍增的主流做法。
# 倍增法的基础应用
## 快速幂
:::info[快速幂是倍增还是分治？]
倍增还有一个应用是**快速幂**，同时也是分治的一个绝佳体现。
但对于**快速幂是倍增还是分治**这个问题，我认为，它们只是看问题的角度不同。
- 要是从 $a^n$ 入手，将它**递归地**拆成 $a^{\frac n2}\cdot a^{\frac n2}$，那它就是**分治**。
- 要是从 $a$ 入手，把指数 $n$ 写成二进制，从最低位开始扫描，那它就是**倍增**。
不管是从上往下（分治），还是从下往上（倍增），它们本质上都没有区别。
~~这和问动态规划是递推还是记忆化搜索一样。~~
:::
:::epigraph[]
这里仅展示快速幂的倍增做法。
:::
**问题**：计算 $a^n\bmod p$，其中 $a,n,p$ 均为正整数。
既然是二进制倍增，直接把 $n$ 拆成二进制 $(n)_2$。
这里先假设 $n=13$，则 $a^{13}=a^{8+4+1}=a^8\cdot a^4\cdot a$。
似乎还看不出，那再细分 $a^{13}=1\cdot a^8\times1\cdot a^{4}\times 0\cdot a^{2}\times1\cdot a$，而 $13=(1101)_2$，刚好与不同次数的 $a$ 对应。
因此，倍增快速幂的做法如下：
1. 将 $n$ 拆为 $(n)_2$，记录答案 $\mathrm{ans}\gets1$。
2. 从右往左依次计算，对于 $(n)_2$ 的第 $k$ 个二进制位（$0\leqslant k\leqslant\lfloor\log_2n\rfloor$），若该位是 $1$，则记录位权 $w=2^k$，可得 $\mathrm{ans}\gets \mathrm{ans}\cdot a^{w}$。
注意到快速幂的 $a$ 的各个指数呈 $2^k$ 增加，于是可定义 $\mathrm{base}$ 记录 $a^w$，方便计算。
初始化当然是 $\mathrm{base}\gets a$。
转移是 $\mathrm{base}\gets\mathrm{base}^2$，体现快速幂性质。
但注意转移时还需要对 $p$ 取模，真正的转移是
$$\mathrm{base}\gets(\mathrm{base}\bmod p)^2$$
最后，不要忘记每次计算后的 $\mathrm{ans}$ 需要 $\mathrm{ans}\gets\mathrm{ans}\bmod p$。
故倍增快速幂的函数为
```cpp
int quickPower(int a,int n,int p){
int ans=1;
long long base=a;
while (n){
if (n&1) ans*=base;
n>>=1;
base=(base%p)*(base%p);
ans%=p;
}
return ans%p;
}
```
## ST 表（Sparse Table）
ST 表主要解决**区间最值查找**（RMQ）问题，它的实现方法就用到了倍增。
以模板题 [洛谷 P3865 ST 表 & RMQ 问题](https://www.luogu.com.cn/problem/P3865) 为例讲解。
---
我们要求得一个**区间**的最大值，根据倍增法，自然就想到**预处理长度为 $2^k$ 的区间的最大值**，然后通过两个区间的覆盖来得出被求区间的最大值，显然，两个重叠的区间并不影响整个区间的最大值。
了解这个后，定义状态 $f_{i,k}$，表示该区间的左端点为 $i$，长度为 $2^k$。
显然有初始化：$\forall~i\in[1,n],~f_{i,0}=a_i$。
因为长度为 $2^0=1$ 的区间最大值显然只能是里面唯一一个元素 $a_i$。
预处理 $f_{i,k}$ 是这样的步骤：
1. 显然，$f_{i,k}$（$k\geqslant1$）由两个长度为 $2^{k-1}$ 的区间拼凑而成。
2. 要求那两个长度为 $2^{k-1}$ 的区间，必须知道它们的左端点。
- 左区间的左端点显然就是 $i$。
- 右区间的左端点是什么呢？因为左区间的左端点为 $i$，长度为 $2^{k-1}$，那么右区间的左端点就必然为 $i+2^{k-1}$ 了。
3. 最后，左、右区间合并，$f_{i,k}$ 的最大值，取两个子区间最大值的较大者，得到
$$f_{i,k}=\max\left(f_{i,k-1},~f_{i+2^{k-1},k-1}\right)$$
预处理解决了，接下来就要解决区间 $[l,r]$ 的最大值了。
我们取预处理的两个区间 $A,B$，$A$ 区间的左端点为 $l$，$B$ 区间的右端点为 $r$。两者可能有重叠部分，但不影响 $[l,r]$ 的最大值。更重要的是，$A\cup B\subseteq[l,r]$，否则计算到 $[l,r]$ 外边了。
我们先把 $[l,r]$ 的长度算出来，得到 $\mathrm{len}=r-l+1$，只有这样我们才能定位区间。
接着得到 $k=\lfloor\log_2\mathrm{len}\rfloor$，这是为了把 $[l,r]$ 拆成两半。
那么，$A$ 区间就是 $f_{l,k}$，而 $B$ 区间的右端点为 $r$、长度为 $2^k$，得到左端点为 $r-2^k+1$。
最后得到结果：
$$\max\left(f_{l,k},~f_{r-2^k+1,k}\right)$$
代码如下：
```
#include <bits/stdc++.h>
using namespace std;
int n,m,a[100005],f[100005][25];
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i){
scanf("%d",&a[i]);
f[i][0]=a[i];
}
//预处理
for (int k=1;(1<<k)<=n;++k)
for (int i=1;i+(1<<k)-1<=n;++i)
f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
while (m--){
int l,r;
scanf("%d%d",&l,&r);
int k=log2(r-l+1);
printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k]));
}
return 0;
}
```
:::info[为什么预处理时 $k$ 在外层？]
因为 $k$ 起到**限定区间长度**的作用，保证 $2^k\leqslant n$，这就能让右区间的左端点 $i+2^{k-1}$ 始终不会越界。而 $i+2^k-1\leqslant n$ 确保区间右端点不越界，当 $i+2^k-1>n$ 时，右区间长度是一个负数，这是非法操作，而当 $i+2^k-1=n$ 时，$f_{i,k}$ 就是左区间的值，**这点不可忽略**。
:::
## 最近公共祖先（LCA）
**公共祖先**的定义：在一棵树上，对于两节点 $x,y$，若节点 $u$ 既是 $x$ 的祖节点，又是 $y$ 的祖节点，则称节点 $u$ 为节点 $x,y$ 的公共祖先。
**最近公共祖先**的定义：在一棵树上，对于两节点 $x,y$ 的公共祖先 $u$，当节点 $u$ 的深度最大时，就被称为最近公共祖先。
> **自定义符号**：
> - $\mathrm{dep}_u$：节点 $u$ 的深度（根节点的深度为 $0$）。
> - $\mathrm{LCA}_{u,v}$：节点 $u,v$ 的 LCA。
> - $\operatorname{son}(u)$：以节点 $u$ 为根节点的子树的子节点集合。
以模板题 [洛谷 P3379 最近公共祖先](https://www.luogu.com.cn/problem/P3379) 为例题讲解。
---
题目给定一棵树和若干次节点 $a,b$ 询问，要求 $\mathrm{LCA}_{a,b}$。
不难想到，若 $\mathrm{dep}_a\leqslant\mathrm{dep}_b$（即 $a$ 在 $b$ 的**上面**），则一定有 $\mathrm{dep}_{\mathrm{LCA}_{a,b}}\leqslant\mathrm{dep}_a$。毕竟 LCA 一定是两节点的祖先，不可能还在它们的下面。
可以想到**暴力跳**代码，先把较深的节点往上挪，直到两节点的深度相同。接着两者一齐向上跳，每次都跳到它们的父节点（深度减 $1$），由于除根外任意节点都有唯一一个父节点，两者总能跳到一个节点，这个节点就是两者的 LCA。
根据思路可知，除了建树，我们还需要维护 $n$ 个节点的深度 $\mathrm{dep}_i$、$n$ 个节点的父节点 $\mathrm{fa}_i$。
这是[暴力跳的记录](https://www.luogu.com.cn/record/276472085)。分析计算复杂度：
- 时间复杂度：建树 $O(n)$，单次 LCA 最坏情况 $O(n)$，总为 $O(n)+m\cdot O(n)=O(nm)$。
- 空间复杂度：总为 $O(n)$。
在 $1\leqslant n,m\leqslant5\times10^5$ 的数据下，时间达到 $2.5\times10^9$，超时。
---
:::epigraph[**倍增 LCA 引言**]
既然一步一步跳这么费劲，那用倍增思想，进行**二进制**跳，不就能把因子 $n$ 变成 $\log_2n$ 了嘛！
:::
由于公共祖先是节点不断堆叠父节点形成的，就把 $\mathrm{fa}$ 设成状态即可（后续称 $f$）。
既然要**二进制**跳，肯定要记录跳的步数 $2^k$ 啊，定义 $f_{k,i}$，表示节点 $i$ 跳 $2^k$ 步到达的祖先。
显然有初始化 $\forall~v\in\operatorname{son}(u),~f_{0,v}=u$，毕竟跳 $2^0=1$ 步肯定是父节点了。
接着转移，想到如果你要跳 $2^k$ 步到某个祖先，可以尝试先跳 $2^{k-1}$ 步，再跳 $2^{k-1}$ 步，两次跳祖先后就能达到跳 $2^k$ 步的效果。
转移方程如下：
$$f_{k,u}=f_{k-1,f_{k-1,u}}$$
预处理完之后，就按照暴力跳的基本思路：
1. 将较深节点向上移。
2. 两者一齐向上移。
两步均使用倍增完成。
> 这里，我们令 $a$ 为较深节点，可使用 `swap(a,b)` 把较深节点换到 $a$。
首先，要想把较深节点向上移，肯定要知道它们的相对深度，即 $\mathrm{diff}=\mathrm{dep}_a-\mathrm{dep}_b$。
把 $\mathrm{diff}$ 拆成二进制 $(\mathrm{diff})_2$，判断**是否要跳**，不断向上跳即可。
```cpp
for (int k=19;k>=0;--k) if (diff&(1<<k)) a=fa[k][a];
```
> **注**：`diff&(1<<k)` 表示求 $(\mathrm{diff})_2$ 的第 $k$ 位。
然后就是将深度相同的两节点 $a,b$ 按照同样的思路，一齐向上跳，直到它们的父节点相同为止。此时，它们的父节点就必然是两者的 LCA 了。
```cpp
for (int k=19;k>=0;--k){
if (fa[k][a]!=fa[k][b]){
a=fa[k][a];
b=fa[k][b];
}
}
/*------------------------*/
//或者也可以这样写：
for (int k=19;k>=0;--k){
if (fa[k][a]==fa[k][b]) continue;
a=fa[k][a];
b=fa[k][b];
}
/*------------------------*/
return fa[0][a]; //再跳一步就是两者的 LCA 了
```
> 注意不要忘加 `if (a==b) return a` 特判 $a,b$ 本身有祖孙关系。
::::info[正确性说明]
:::epigraph[]
由于第一、二份代码等价，本次分析以**第二份代码**为主。
:::
起跳时，$a,b$ 必定处于 $\mathrm{LCA}_{a,b}$ 下。
在跳 $2^k$ 步时，代码会先判断：**$f_{k,a}$ 和 $f_{k,b}$ 是不是同一个节点？**
有且只有两种情况：
- **若它俩是同一个节点**：这说明 $2^k$ 这个步长，已经足够让 $a$ 和 $b$ 在 LCA 或其祖先处汇合了。这意味着我们可能跳过头。执行 `continue`，等下一轮**更短的步长**。
- **若它俩不是同一个节点**：这说明即使跳了 $2^k$ 步，$a$ 和 $b$ 的祖先依然不同。这保证了 LCA 一定还在上面。跳 $2^k$ 步是决不会超过 LCA 的。
::::
主要代码如下：
```cpp
void depth(int u,int dad){
fa[0][u]=dad;
dep[u]=dep[dad]+1;
for (int k=1;k<20;++k) fa[k][u]=fa[k-1][fa[k-1][u]];
for (const auto &v:g[u]){
if (v==dad) continue;
depth(v,u);
}
}
int LCA(int a,int b){
if (dep[a]<dep[b]) std::swap(a,b);
int diff=dep[a]-dep[b];
for (int k=19;k>=0;--k) if (diff&(1<<k)) a=fa[k][a];
if (a==b) return a;
for (int k=19;k>=0;--k) if (fa[k][a]!=fa[k][b]) {a=fa[k][a];b=fa[k][b];}
return fa[0][a];
}
```
分析计算复杂度：
- 时间复杂度：建树 $O(n)$，单次 LCA 要 $O(\log_2n)$，总时间为 $O(m\log_2n)$。
- 空间复杂度：维护深度 $O(n)$，倍增数组 $O(nk)=O(n\log_2n)$，总为 $O(n\log_2n)$。
# 倍增法的变种应用
:::epigraph[**阅读提示**]
该部分主要展示思路。与题解不同，本文会很详细说明思路和思考方法。
:::
## [洛谷 P4155 国旗计划](https://www.luogu.com.cn/problem/P4155)
> 自定义的简写：
> - 区间 $a$：编号为 $a$ 的区间。
**审题**：本题要在一个环上挑选部分小区间来覆盖整个区间。
考虑到需要统计数据，肯定要存**编号**（$\mathrm{id}$）。又想到我们要尽可能少覆盖区间，但区间长度不定，因此再定义每个区间的**左端点**（$l$）与**右端点**（$r$）。
又发现本题是**环**，自然想到**断环成链**，数组空间要开 $2\times N$。
```cpp
struct Range{
int id; //编号
int l; //区间 id 的左端点
int r; //区间 id 的右端点
}s[N*2];
```
> **简写声明**：后续的 $s[i]_r$ 等价于 `s[i].r`，其它成员变量亦如此。
```cpp
for (int i=1;i<=n;++i){
scanf("%d%d",&s[i].l,&s[i].r);
if (s[i].r<s[i].l) s[i].r+=m; //当区间跨越链时，断环成链
s[i].id=i;
}
//断环成链基本步骤
for(int i=1;i<=n;++i){
s[i+n]=s[i];
s[i+n].l=s[i].l+m;
s[i+n].r=s[i].r+m;
}
```
定义函数 `fun(x)`，表示当第 $x$ 个区间必须选择时，至少需要多少个区间才能覆盖整个区间。
:::epigraph[]
着重讲述函数 `fun(x)` 的全过程思路。
:::
既然要统计区间个数，那肯定要有一个计数器 $\mathrm{cnt}$，又区间 $x$ 必选，故初始化 $\mathrm{cnt}\gets1$。
既然要覆盖区间，那必须知道**是否覆盖完区间**，就要知道**最终覆盖处**与**当前最远覆盖处**，于是定义 $\mathrm{end}$ 表示**最终覆盖处**，定义 $\mathrm{now}$ 表示**当前最远覆盖处**。也可以说 $\mathrm{now}$ 表示已覆盖的总区间的右端点。
由于区间 $x$ 都被选了，最开始最远肯定会覆盖到 $s[x]_r$，则初始化 $\mathrm{now}\gets s[x]_l$。
$\mathrm{end}$ 的确定更好办：知道要从区间 $x$ 开始，那起点就是 $s[x].l$，又环的周长是 $m$，因此可确定最终覆盖处就是 $\mathrm{end}\gets s[x]_l+m$。
不难想到，若 $\mathrm{now}$ 超过了 $\mathrm{end}$，则必定说明已经覆盖完毕。
为确保 $\mathrm{now}$ 不被污染，我们可以定义临时变量 $\mathrm{maxx}\gets\mathrm{now}$，表示该次覆盖最远可到何处。
### 暴力做法
由于已经把环断成链了，因此需要统计到 $2n$，设当前区间为 $i$。
首先，我会想到需要保证**区间 $(i+1)$ 必须能接得上区间 $i$ 才行**，换句话说，就是下一区间的左端点必须在当前区间的**区间内**，而区间已覆盖区间的右端点是 $\mathrm{now}$，因此必须保证 $s[i]_l\leqslant \mathrm{now}$。
接着，既然想覆盖到更远**而不缩水**，显然要保证 $s[i]_r>\mathrm{maxx}$，否则越覆盖越小。
故选择过程中，$\mathrm{maxx}$ 的“打擂台”过程就是
$$\mathrm{maxx}\gets s[i]_r,~\text{当 }x[i]_l\leqslant\mathrm{now}\text{ 且 }s[i].r>\mathrm{maxx}$$
::::epigraph[**思路总结**]
显而易见的贪心思路：每次覆盖得越远，所用的区间数量就越少。
::::
经过 $2n$ 轮选择，最终 $\mathrm{maxx}$ 是第 $i$ 轮选出的**覆盖最远的右端点**，故最后 $\mathrm{now}\gets\mathrm{maxx}$。同时，选了一个区间，每次都要 $\mathrm{cnt}\gets\mathrm{cnt}+1$。
代码如下：
```cpp
int fun(int x){
int now=s[x].r, end=s[x].l+m, cnt=1;
while (now<end){
int maxx=now;
for (int i=1;i<=2*n;++i) if (s[i].l<=now&&s[i].r>maxx) maxx=s[i].r;
now=maxx; ++cnt;
} return cnt;
}
```
最后统计结果，输出：
```cpp
for (int i=1;i<=n;++i) ans[s[i].id]=fun(i);
for (int i=1;i<=n;++i) printf("%d ",ans[i]);
```
算法复杂度分析：
- 时间复杂度：单个 `fun(x)` 最坏 $O(n^2)$，总为 $O(n\cdot n^2)=O(n^3)$.
- 空间复杂度：仅用结构体 `s[N]`、最终结果 `ans[N]`，总为 $O(n)$。
[这是](https://www.luogu.com.cn/record/276640214)暴力做法的结果：$3\textcolor{green}{\text{AC}}+7\textcolor{navy}{\text{TLE}}$。
### 倍增做法
:::epigraph[**放在前面**]
倍增本质是一种**优化**，只有知道要优化什么，才能写出倍增。
:::
对于这道题，很明显，我们要优化**选择区间的过程**。
定义状态 $f_{k,i}$，表示从第 $i$ 个区间出发，连续选择 $2^k$ 个区间后，能到达的最后一个区间的编号。
:::info[为什么要这样定义状态？]{open}
我们的目标是：**从起点开始，用最少的区间覆盖整个环**。
在贪心策略下，每一步都会选一个能接上的、终点最远的区间。我们关心的永远是：**跳了若干步后，我最远能覆盖到环上的哪个位置？**
- **区间的位置信息完全由它的终点 $s[i].r$ 决定**。因此，知道最后一个区间是谁，就知道当前覆盖的最远距离。
- 如果我们只记录**跳了多少步**，我们完全不知道覆盖到哪了，就无法判断是否已经覆盖完整个环，也无法知道下一步该从哪开始。
- 如果我们记录**覆盖的最远距离**，那只是一个坐标值。坐标值无法直接告诉我们下一步该选哪个区间去接力，因为区间选择依赖的是区间的起点位置及其贪心属性。
所以，记录**最后一个区间的编号**既能定位当前位置，又能为下一跳提供起点，是最优选择。
:::
在初始化之前，我们先要进行排序：
```cpp
sort(s+1,s+1+n,[](data a,data b){return a.l<b.l});
```
因为，状态 $f$ 需要求最后一个区间的编号，这就要求**右端点单调递增**，而注意到题目保证**任意两区间无包含关系**，因此只要左端点单调递增，右端点必然也单调递增。
:::info[为什么不能对右端点进行排序？]
在本题里，我们使用贪心策略选择下一个区间时，规则是：对于当前区间 $i$，在所有满足 $s[j]_l\leqslant s[i]_r$ 的区间中，选择一个**右端点最远**的区间作为下一跳。
这一策略能够通过双指针高效执行，前提就是区间已经按**左端点从小到大**排序。
因为这样，满足条件的区间在数组中是连续的一段，我们可以用循环，让 $j$ 不断地向后扫描，直到遇到第一个接不上的区间。此时，所有能接上的区间都被 $j$ 遍历过了，其中自然包含了右端点最远的那个，而这个区间正是 $j-1$。
如果按右端点排序：
- **不保证可接上区间的连续性**。因为右端点的顺序与左端点**无关**，可能有某些区间的左端点很大，但因为右端点很小反而排在前面；也可能有区间的左端点非常小，但因为右端点很大而排在后面。这样，能接上的区间会分散在数组各处。
- **双指针失效**。$j$ 想通过一次遍历找到所有能接上的区间几乎不可能，除非每次都遍历整个数组，那复杂度就会退化为 $O(n^2)
为了方便指向区间，先尝试 定义指针 j ，表示经过一系列选择后，指向最终结果。
int j=1;
for (int i=1;i<=2*n;++i){
while (j<=2*n&&s[j].l<=s[i].r) ++j;
f[0][i]=j;
}然而，这会出现问题：当我们在环上查找完后，指针 j 会停在结果区间的下一个区间 。
这是由于 while 的性质决定的：只有当条件不符合时，它才会停止。j 总是认为下一个区间是合法的 ，当我们遇到结果区间 时，j 指向第一个不合法区间 ；当我们遇到第一个不合法区间时，循环跳出，但 j 仍然指向这个不合法区间。
因此，我们改变 j 的定义为经过一系列选择后，指向结果区间的下一个区间。f_{0,i} 的初始化为f_{0,i}\gets j-1 。
总的初始化代码如下：
void init(){
int j=1; //指向第一个不能作为当前区间 i 的接力队友的区间
for (int i=1;i<=2*n;++i){
while (j<=2*n&&s[j].l<=s[i].r) ++j; //保证在环上且能接上
f[0][i]=j-1;
}
for (int k=1;k<20;++k) for (int i=1;i<=n*2;++i) f[k][i]=f[k-1][f[k-1][i]];
}倍增跳步
需知起点 \mathrm{cur}\gets\mathrm{id} 、已选区间数量 \mathrm{cnt}\gets1 、终点 \mathrm{len}\gets s[\mathrm{cur}]_l+m 。
:::epigraph[贪心思想 ]
想到要尽量更快覆盖，尽可能地大步。
:::
定义临时变量 \mathrm{nxt} 表示 \mathrm{cur} 跳 k 步所在的区间，即 \mathrm{nxt}\gets f_{k,\mathrm{cur}} 。\mathrm{nxt} 能不能覆盖完就行了：
若未覆盖完，即 s[\mathrm{nxt}]_r<\mathrm{len} ，则更新 \mathrm{cur}\gets\mathrm{nxt} 、\mathrm{cnt}\gets\mathrm{cnt}+2^k ，再跳较小步。
若已覆盖完，即 s[\mathrm{nxt}]_r\geqslant\mathrm{len} ，退出。
:::align{center}
不要以为答案是 \mathrm{cnt} ！！！
:::
注意到判断规则 ：跳完 2^k 步后，如果覆盖的终点还严格小于 目标，才执行跳跃。s[\mathrm{cur}]_r<\mathrm{len} 的。否则，你在之前的某一轮就会因为条件不满足而没有跳。
:::align{center}
但没跳，不代表做不到
:::
循环结束后，当前的 \mathrm{cur} 区间虽然自己没覆盖完，但它的下一跳（f_{0,\mathrm{cur}} ）一定能覆盖目标。因为程序能运行到这里，就保证了至少存在一个解。int fun(int id){
int cur=id; //当前所在区间的编号
int cnt=1; //已经选了的区间数量
int len=s[cur].l+m; //需要覆盖的最远距离
for (int k=19;k>=0;--k){
int nxt=f[k][cur];
if (s[nxt].r<len) {cur=nxt;cnt+=(1<<k);}
} return cnt+1;
}:::success[完整 \textcolor{green}{\text{AC}} 代码]
#include <bits/stdc++.h>
using namespace std;
constexpr int N=2e5+5;
struct data {int id,l,r;} s[N*2];
int n,m,ans[N],f[20][N*2];
void init(){
int j=1;
for (int i=1;i<=2*n;++i){
while (j<=2*n&&s[j].l<=s[i].r) ++j;
f[0][i]=j-1;
}
for (int k=1;k<20;++k) for (int i=1;i<=n*2;++i) f[k][i]=f[k-1][f[k-1][i]];
}
int fun(int id){
int cur=id,cnt=1,len=s[cur].l+m;
for (int k=19;k>=0;--k){
int nxt=f[k][cur];
if (s[nxt].r<len) {cur=nxt;cnt+=(1<<k);}
} return cnt+1;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i){
scanf("%d%d",&s[i].l,&s[i].r);
if (s[i].r<s[i].l) s[i].r+=m;
s[i].id=i;
} sort(s+1,s+1+n,[](data a,data b) {return a.l<b.l;});
//断环成链
for(int i=1;i<=n;++i) {s[i+n]=s[i];s[i+n].l=s[i].l+m;s[i+n].r=s[i].r+m;}
init(); //初始化
for (int i=1;i<=n;++i) ans[s[i].id]=fun(i);
for (int i=1;i<=n;++i) printf("%d ",ans[i]);
return 0;
}:::
结语
:::epigraph[面向人群 ]
本文主要面向初学倍增的 OIer，也欢迎想要复习倍增的 OIer。
:::
本文讲述了倍增法的两个基础应用（ST 表、LCA）和一个变种应用。
洛谷 P1081 开车旅行
洛谷 P1613 跑路
洛谷 P3509 ZAB-Frog
倍增思想的三步法 ：
定义状态 ：f_{k,i} 表示从 i 出发，经过 2^k 次操作后的结果。关键是用倍增优化什么过程 。预处理 ：f_{k,i}=f_{k-1,f_{k-1,i}} 。本质是大步拆小步 。查询 ：从大到小尝试 k ，能跳就跳。本质是二进制拼凑 。
这三步可解决倍增的大部分基础、变种题。
版权声明
:::epigraph[生成式人工智能使用说明 ]
本文的核心思想、推导过程、代码实现均由本人独立完成。保证本人的贡献远大于 DeepSeek 的贡献。全文的语句通顺度 进行润色。
您需遵守下列条件：
署名 ：您必须给出适当的署名，提供指向本许可协议的链接，并标明是否对原始作品 作了修改。您可以用任何合理的方式来署名，但不得以任何方式暗示许可人为您或您的使用背书。非商业性使用 ：您不得将本作品用于商业目的 。相同方式共享 ：如果您再混合、转换或者基于本作品进行创作，您必须基于与原先相同的许可协议 分发您贡献的作品。