考え方は 公式解説 と同様ですが、各桁の結果をまとめて保持することで、クエリごとにオンラインで \(O(1)\) の計算量でも解くことができます。 \(m=2^{30}-1\) とします。 具体的には、\(i\) 番目のクエリを答える際には
・\(0\) から始めて操作 \(1\) → 操作 \(2\) → ・・・ → 操作 \(i-1\) を行った結果\(s_0\)
・\(m\) から始めて操作 \(1\) → 操作 \(2\) → ・・・ → 操作 \(i-1\) を行った結果 \(s_1\)

の \(2\) つを保持しながら更新すれば良いです。クエリに回答するときは \(i-1\) 番目のクエリが終わった時点の結果 \(x\) のビットのうち \(1\) が立っている部分とそれ以外に分けて考えると、前者は \(x\ \mathrm{and}\ s_1\) 、後者は \((x \ \mathrm{xor}\ m) \ \mathrm{and}\ s_0\) のように計算できます。

AC 例（PyPy3）