E - Maximize XOR

考察

$i \oplus (i+1)$ の挙動に注目します。例えば、$i = 247$ とします。$i, i+1$ の $2$ 進展開は

$i = 247 = 10100111_{(2)}\\ i+1 = 248 = 10101000_{(2)}$

となり xor は

$10100111_{(2)} \oplus 10101000_{(2)} = 00001111_{(2)}$

となります。 $i \oplus (i+1)$ は $i$ と $i+1$ の $2$ 進展開の差異を表します。 $i$ に $1$ を足したものが $i+1$ であるため、$i \oplus (i+1)$ は本質的に「$i$ に $1$ を足したとき、二進表記で繰り上がりがどこまで起きるか」を表します。

よって、 $i \oplus (i+1)$ は $i$ の $2$ 進展開の最下位の桁から $1$ がどれだけ続くか (Count Trailing Ones) を数えれば分かります。例えば $i=247= 10100111_{(2)}$ なら、$1$ は最下位から $3$ 桁続いているため、繰り上がりが $3$ 回発生し、$i, i+1$ の bit の差異は $1111_{(2)}$ です。よって、$i\oplus(i+1) = 1111_{(2)}$ になります。

厳密に： $i \equiv 2^{k} - 1 \pmod{2^{k+1}}$ とします (この非負整数 $k$ は各 $i$ に対して一意に存在する)。このとき $i \oplus (i+1) = 2^{k+1}-1$ です。例として、 $i=247= 10100111_{(2)}$ なら、$i \equiv 7 \pmod{16}$ すなわち $i \equiv 2^{3} - 1 \pmod{2^4}$ なので、$i \oplus (i+1) = 2^4-1 = 15$ です。

解法

$f(i)$ を、$i \equiv 2^{k} - 1 \pmod{2^{k+1}}$ を満たす唯一の $k$ とおきます。求めるべきは、$L \le i \le R$ であって $f(i)$ が最大になるようなものです。

制約下で $f(i) \le 60$ なので、$k = 60, 59, 58, \cdots, 0$ ごとに $L \le i \le R$ であって $f(i) = k$ となるようなものの個数を求めて、それが $1$ 個以上あればよいことになります。

$n$ 以下の非負整数であって $f(i)=k$ となるものの個数を $S_{n,k}$ とすると、

$\displaystyle S_{n,k} = \left\lfloor \frac{n+2^{k}+1}{2^{k+1}} \right\rfloor$

です。$L \le i \le R$ であって $f(i)=k$ となるようなものの個数は $S_{R,k} - S_{L-1,k}$ 個あるため、$O(\log R)$ でこの問題が解けました。