本問題は、Sparse Table と呼ばれるデータ構造をもとにしています。

以下、\(l \leq r\) を満たす整数 \(l, r\) について、 \(l\) 以上 \(r\) 以下の整数全体からなる集合を区間 \([l, r]\) と呼びます。すなわち \([l, r] \coloneqq \lbrace l, l+1, l+2, \ldots, r\rbrace\) です。 また、区間 \([l, r]\) の長さをその要素数 \(r-l+1\) で定義します。

本問題は、\(M\) 個の区間を予め適切に選んでおくことで、\([1, N]\) の部分集合である任意の区間 \([L, R]\) を、予め選んだ \(2\) つの区間の和集合として表す問題です。

結論を述べると、\(M\) 個の区間として下記のものをすべて選べば良いです。

• \([1, N]\) の部分集合であって、長さ \(1\) の区間すべて
• \([1, N]\) の部分集合であって、長さ \(2\) の区間すべて
• \([1, N]\) の部分集合であって、長さ \(4\) の区間すべて
• \(\cdots\)
• \([1, N]\) の部分集合であって、長さ \(2^{\lfloor \log_2 N \rfloor}\) の区間すべて

例えば、\(N = 10\) の場合、

• 長さ \(1\) の区間： \([1, 1], [2, 2], \ldots, [10, 10]\) の \(10\) 個
• 長さ \(2\) の区間： \([1, 2], [2, 3], \ldots, [9, 10]\) の \(9\) 個
• 長さ \(4\) の区間： \([1, 4], [2, 5], \ldots, [7, 10]\) の \(7\) 個
• 長さ \(8\) の区間： \([1, 8], [2, 9], \ldots, [3, 10]\) の \(3\) 個

の計 \(29\) 個を選びます。

この選び方において、各長さの区間を選ぶ個数は高々 \(N\) 個であり、選ぶ長さの種類は \(\lfloor \log_2 N \rfloor + 1\) 種類ですので、 \(M \leq N(\lfloor \log_2 N \rfloor + 1)\) です。 最大ケース \(N = 4000\) においても、\(M \leq 4000 \times (\lfloor \log_2 4000 \rfloor + 1) = 48000\) であり、\(M\) は上限である \(50000\) 以下におさまります。

また、クエリとして与えられた区間 \([L, R]\) は、 \(2^K \leq R-L+1\) を満たす最大の整数を \(K\) として、 区間 \([L, L+2^K-1]\) と区間 \([R-2^K+1, R]\) という、予め上で選んでおいた \(2\) つの区間の和集合として表せます。

以上より、上述の方法で \(M\) 個の区間を選ぶことで本問題に正解できます。

Sparse Table について

本問題のもととなった Sparse Table について、簡単に述べます。

Sparse Table は、例えば、長さ \(N\) の固定された配列 \(A\) について、与えられた区間 \([L, R]\) における \(A\) の最小値 \(\min_{i \in [L, R]} A[i]\) を高速に求めるクエリを \(O(1)\) 時間で処理できるデータ構造です。

その仕組みは、上の解説本編で選んだ、 \([1, N]\) の部分集合であって長さ \(1, 2, 4, \ldots, 2^{\lfloor \log_2 N \rfloor}\) の区間すべて（計 \(O(N \log N)\) 個）について、各区間での \(A\) の最小値を前計算しておくというものです。

すると、区間 \([L, R]\) における \(A\) の最小値を求めるクエリを処理するには、 解説本編に述べたように \([L, R]\) を \([L, L+2^K-1]\) と \([R-2^K+1, R]\) の和集合に分解し、 前計算しておいた、\([L, L+2^K-1]\) における最小値と \([R-2^K+1, R]\) における最小値の小さい方を出力すれば良いです。

前計算の処理は、 区間 \([L, L+2^k-1]\) における最小値が、区間 \([L, L+2^{k-1}-1]\) における最小値と区間 \([L+2^{k-1}, L+2^k-1]\) における最小値の小さい方として求まることを用いると、\(k\) が小さいものから順に計算することで、全体で \(O(N \log N)\) 時間で行うことができます。

最小値のところを、最大値、ビットごとの論理和・論理積、最大公約数などいくつかの他の演算に置き換えた場合にも、同様に Sparse Table を用いることができます。 また、Sparse Table を改良した Disjoint Sparse Table と呼ばれるものもあるので、興味のある方はぜひ調べてみてください。