一見するとソートして二分探索で行けそうな気がするが, \(Q\) が大きいので \(O(N\log N + Q\log N)\) は2つめの \(\log N\) の分で通らない.

\(a_i\) は乱数で生成されているので, ほぼ一様分布とみなせる. \([0, 2^{31})\) の空間を分割し, 上位 \(k\) ビットごとに存在する数を数え, 累積和を取っておく.

こうすることで, 1つの分割部に入る数値の数は期待値として1つ程度なので, ほぼ \(O(1)\) でクエリの結果を得ることができる.

\(k\) をいくつに設定するかであるが, 15 あたりが最も速くなった.