着想は公式解説とほぼ同じなのでかなり簡潔に記します。
問題概要
考えたこと
掃き出し法っぽい操作ができればよい。
A_i を区間 [i, i] であると考えて A(i, i) とする。
(k-1)-bit 目まで全て 0 であるような A(l, r) について、r の小さい順に見ていく。
- A(l, r) の k-bit 目が 0 → 何もしない
- A(l, r) の k-bit 目が 1 → 同じく k-bit 目が 1 であるような最も近い A(p, q) とマージ
を行うことで、全ての A(l, r) の k-bit 目を 0 にすることができる。
ここで「最も近い」とは、q ≦ r であるような A(p, q) のうち最も p の大きいものをいう。マージすると値は A(l, r) xor A(p, q)、区間は [min(l, p), r] となる。
これにより、k-bit 目まで全て 0 であるような A(l, r) を新たに作成できる。また、既存の A(l, r) は少なくとも 1 回は新たな A(l, r) の作成に寄与しているため、いわゆる情報落ちも発生していない（おそらく長くなるので割愛）。
あとは、X(L, R) に対して L ≦ l かつ r ≦ R であるような任意の A(l, r) を用いて掃き出していけばよい。X(L, R) を 0 にすることができれば X(L, R) が作成可能であると言える。
計算量は各 bit に対して O(n) なので全体で O(n log(max {A})) である。
新たに作成した A(l, r) のソートはマージソートが可能なので log を 1 つ落とせる。
提出コード
定数倍削減をサボったので少し遅め。
