大约是翻译了一下官方题解？

§ @Description@

对于一个整数序列 $P=(P_{1},\dots,P_{m})$，定义 $f(P)$ 为一个序列 $Q$ 满足：

• $Q_{i}=P_{i}+P_{i+1}$，其中 $i\in[1,m)$；
• $f(P)=(P_{1},Q_{1},\dots,P_{m-1},Q_{m-1},P_{m})$。

给出正整数 $a,b,N$，其中 $a,b\leqslant N$，令序列 $A=(a,b)$，令序列 $B$ 为一下操作的结果：

• 做 $N$ 次令 $A=f(A)$.
• 删除 $A$ 中大于 $B$ 的数。

求 $B_{l,\dots r}$。

§ @Solution@

∆ ◆ The Coefficient Sequence

构造最终的 $A$ 序列的过程是这样的：

$$a,b \\ a,a+b,b \\ a,2a+b,a+b,a+2b,b \\ a,3a+b,2a+b,3a+2b,a+b,2a+3b,a+2b,a+3b,b \\ \dots$$

可以发现有对称性。此时我们先不关心 $a,b$ 以及 $N$ 的大小，反之，我们来观察其序列系数，也就是把每个元素看成 $xa+yb$，其系数的 $(x,y)$，上例的序列系数即

$$(1,0),(0,1) \\ (1,0),(1,1),(0,1) \\ (1,0),(2,1),(1,1),(1,2),(0,1) \\ (1,0),(3,1),(2,1),(3,2),(1,1),(2,3),(1,2),(1,3),(0,1) \\ \dots$$

以下我们称其为 Coefficient Sequence。

∆ ◆ The properties of the Coefficient Sequence

现在我们来观察 Coefficient Sequence 的性质。

Observation 1：在 Coefficient Sequence 中相邻的两个二元组 $(x_{S},y_{S}),(x_{T},y_{T})$，都有： $x_{S}y_{T}-x_{T}y_{S}=1$。

使用数学归纳法（induction）即证。

Observation 2：对于两个 两个二元组 $(x_{S},y_{S}),(x_{T},y_{T})$，如果他们满足 $x_{S}y_{T}-x_{T}y_{S}=1$，那么它们在 Coefficient Sequence 中相邻，即 Observation 1 是充要条件。

不会证，大概意会一下吧。

Observation 3：对于一个二元组 $(x,y)$，如果 $\gcd(x,y)=1$，那么 $(x,y)$ 会出现在 Coefficient Sequence 中。

比较显然，以至于官方题解没有给出证明。

Observation 4：在任意时刻，所有在 Coefficient Sequence 中的 $(x,y)$ 总是呈从左到右的关于值 $\frac{y}{x}$ 递增（令 $\frac{x}{0}=\infty$）。

∆ ◆ The sequence $B$ in other words

现在描述序列 $B$ 变得更加容易，现在我们这样描述它：

对于所有二元组 $(x,y)$ 满足 $x,y,s.t.x,y\in\mathbb{N},\gcd(x,y)=1,ax+by\leqslant N$，我们对其按 $\frac{y}{x}$ 排序后形成一个二元组序列 $\{(x_{i},y_{i})\}$，则 $B_{i}=ax_{i}+by_{i}$。

∆ ◆ Computing $B_{n}$

现在我们来考虑原问题的简化版，我们来计算 $B_{n}$。让我们把这个描述成一个计数问题（通过二分 $\frac{y}{x}$）：

给定正整数 $a,b,N$，以及一个有理数 $c$（二分的值），求二元组 $(x,y)\neq(0,0)$ 的数量，其中 $(x,y)$ 满足

• $ax+by\leqslant N$；
• $\gcd(x,y)=1$；
• $\frac{y}{x}\leqslant c$。

我们令 $F(N)$ 为以上问题的答案，同时令 $G(N)$ 为去掉 $\gcd(x,y)=1$ 限制的答案。$G(N)$ 的式子可以很方便的写出来： $G(N)=\sum_{y=1}^{N}\max\{\lfloor\frac{N-by}{a}\rfloor-\lfloor\frac{y}{c}\rfloor+1,0\}$，同时我们还可以写出 $G(N)=\sum_{d=1}^{N}F(\lfloor\frac{N}{d}\rfloor)$。那么再根据 Möbius inversion formula，我们可以表示出 $F(N)=\sum_{d=1}^{N}\mu(d)G(\lfloor\frac{N}{d}\rfloor)$。于是计算该问题答案的复杂度就是 $\mathcal{O}(N)$。

但是此时我们知道了 $B_{n}$ 的 $\frac{y_{n}}{x_{n}}$，怎么知道 $(x_{n},y_{n})$ 呢？我们可以再做一个二分。观察出这样一个规律：若令 $l=(1,0),r=(0,1)$，那么中间位置就是 $l+r$。于是我们可以再次做一个二分，利用 $\frac{y}{x}$ 单调来做 check。

顺带一提，这个还可以使用 类欧几里得 来计算。

∆ ◆ Computing $B_{l,\dots,r}$

可以发现这个东西可以知二求一，于是求出 $B_{l},B_{l+1}$ 就行了。当然也可以求出 $B_{l},B_{r}$ 然后做二分搜索。