概要
解法
$O(NQ)$ 時間計算量の解法で AC になりました。非想定計算量でしょうかね。
$L = \lg \max A_i \leq 30$ とします。
区間 $[L,R)$ が与えられたとき、$$(A_L \operatorname{AND} \cdots\operatorname{AND} A_{M-1}) – (A_M \operatorname{XOR}\cdots \operatorname{XOR} A_{R-1})$$ を求めるクエリに答える問題です。
$L$ を固定して $M$ を増加させていくとき、$\operatorname{AND}$ の値の減少は高々 $L$ 回しか起こらず、ほとんどの区間で定数です。それらの区間は、例えば sparse table を使って $1$ 区間あたり $O(\log N)$ 時間で求めることができます。
さらに、$A_i$ の $\operatorname{XOR}$ に関する累積和を $B_i$ とすることで、ひとつのクエリは次の形の $L$ 個以下のクエリに帰着できます：
- $\min_{L\leq i\leq R}(x \operatorname{XOR} B_i)$ を求めよ
このクエリは愚直にやると $O(R-L)$ 時間ですが、分解したクエリの区間長の総和は $N$ 以下なので、合計で $O(N)$ 時間です。よって、全体として $O(NQ)$ 時間で解くことができます。
コメント
bit 演算と $\min$ だけで処理が簡潔なうえ、CPU がベクトル化できるタイプの計算であるため、実装次第でかなり高速みたいなことだと思います（この辺、あまり正確に語れない）。
他の方の提出を見ていくと、Binary Trie を永続化すると $O(NL^2)$ 時間で解けるっぽいです。私は実装していないので、すこし怪しいですが、理解した範囲で説明を書きます。
永続化とは、データ構造のある処理時点での構造にアクセスする仕組みですが、
- Binary Trie に、$B_1, B_2, \ldots, $ 順に要素を追加していく
- 「$B_R$ まで追加した時点」のデータ構造を利用して、$\min_{L\leq i\leq R}(x \operatorname{XOR} B_i)$ を計算する
という仕組みで解いています。Binary Trie における $x \operatorname{XOR} B_i$ の最小化に際しては、各ノードにおいて、左右の部分木に少なくともひとつの $B_i$ が含まれるかが分かればよいです。特に、$L\leq i$ の範囲の $B_i$ に対してのみこれを行うためには、Binary Trie の各ノードに付加構造として「部分木に含まれる $B_i$ のうち $i$ が最大のもの」を持たせておけばよいです。
