与えられた \((L, R)\) に対して、\((l_i, r_i)\) がわかっている状態で \((l_{i+1}, r_{i+1})\) を \(O(1)\) 時間で求められればよいです（ここで \(r_i < R\) とします）。 これは、

与えられた \((L, R)\) に対して、ABC 349 D で言うところの \((l_1, r_1)\) を \(O(1)\) 時間で求めてください。

という問題で \((r_i, R)\) が与えられるケースに帰着できます。

また、\(l_1 = L\) なので、以下では \(r_1\) を \(O(1)\) 時間で求めることだけ考えます。

公式解説 も適宜参考にしてください。

セグ木において、\(L\) を左端とする区間幅全体からなる集合 \(A\) は

\(\gdef{\ctz}{\operatorname{ctz}}\) \(\gdef\hfloor#1{\lfloor\hspace{-.25em}\lfloor#1\rfloor\hspace{-.25em}\rfloor}\)

\[ \begin{aligned} A &= \{2^i\mid (L\bmod 2^i) = 0\} \\ &= \{1, 2, 4, \dots, 2^{\ctz(L)}\} \end{aligned} \]

と表せます。ただし、\(\ctz(n)\) は \(n\) を 2 進法で表したときの末尾の \(0\) の個数とし、\(\ctz(0)=\infty\) とします。

さて、\(r_1\) は次のように表せます。

\[ \begin{aligned} r_1 &= \max_{j\in A} {\{L+j\mid L+j\le R\}} \\ &= \max_{j\in A} {\{L+j \mid j \le R-L\}}. \end{aligned} \]

すなわち、

\[ \begin{aligned} r_1 &= \max_{0\le i\le\ctz(L)} {\{L+2^i \mid 2^i\le R-L\}} \\ &= L + \min{\{2^{\ctz(L)}, \hfloor{R-L}\}} \end{aligned} \]

となります。ここで、\(\hfloor n\) は \(n\) 以下の最大の 2 べきの整数を表します。

あとは \(2^{\ctz(n)}\) と \(\hfloor n\) を \(O(1)\) 時間で求められればよいです。

\(n\ge 1\) に対して \(2^{\ctz(n)}\) は「\(n\) を 2 進法で表したときに、一番右にある \(1\) 以外の桁を \(0\) にしたもの」に相当します。これは、ビット演算を用いて n & (!n + 1) や（2 の補数表現を前提として）n & -n と書けることが広く知られています。

\(\hfloor n\) に関しては、たとえば「\(n\) を 2 進法で表したときに、一番左にある \(1\) が \(2^k\) の位であるとして \(2^k\)」として求められます。 これは、word RAM においては \(O(1)\) 時間で求められることが（\(2^{\ctz(n)}\) ほどは有名ではなさそうですが）知られています。

• 関連記事 1
• 関連記事 2

また、Rust のような言語では、整数に .next_power_of_two() や .is_power_of_two() のようなメソッドも用意されています（計算量規定はなさそうです）。

提出 #52366131