D - Divide Interval 解説 by rsk0315

O(M) 時間の解法

与えられた \((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)}\) ほどは有名ではなさそうですが)知られています。

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


提出 #52366131

投稿日時:
最終更新: