本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-26 00:03:44

本篇题解是赛后补的，参考学习了官方题解以及 jiangly dalao 的代码。

首先发现本题和最近的 ABC349D 很像。但是注意到那个题里没法将两个区间相减，但是本题可以，于是那个题的策略没法照搬。

那么怎么样才能得到最优解呢？（题目要求我们必须用最优策略）

换句话说，我们需要求出从 $r$ 走到 $l$ 的最少步数。注意到值域相比上一个题小了很多，那么可以尝试最短路。

不难发现，对于一个数 $u$，我们能够转移到的数是 $v = u \pm 2^j, 0\le j \le \mathrm {lowbit}(u)$，其中 $\mathrm{lowbit}(x)$ 是 $x$ 的最低非零位。因为对于 $j \gt\mathrm{lowbit}(u)$，$2^j \nmid u$，无法转移。

由于边权都是 $1$，我们就可以直接 BFS 跑出最短路，然后一边跳一边计算即可。

赛后的 submission