前置き

この解説では、線形代数の用語を使います。理解できる方は、この節を読み飛ばして頂いても構いません。

\(0\) 以上 \(2^{60}\) 未満の整数は、その二進表記を考えることで、各成分が \(0, 1\) であるような \(60\) 次元のベクトルとみなすことができます。
排他的論理和 \(\mathrm{xor}\) をとる操作は、各成分ごとに \(\bmod \, 2\) で和をとることに対応し、整数の集合からいくつかを選んで \(\mathrm{xor}\) をとる操作は、ベクトルに \(0, 1\) 倍したものを \(\bmod \, 2\) で足し合わせることに対応します。
いくつかのベクトルをスカラー倍して足し合わせたものを線形結合と呼びます。

解説における \(\mathrm{span}(X)\) は、整数の集合に対し、いくつかの要素を選んで \(\mathrm{xor}\) をとった値としてあり得るもの全体の集合に対応します。

解法

\(0\) 以上 \(2^{60}\) 未満の整数は、\(60\) 次元数ベクトル空間 \({ \mathbb{F}_2}^{60}\) の元に対応し、整数の集合からいくつかを選んだときの \(\mathrm{xor}\) は、ベクトルの線形結合に対応します。以下では、ベクトルの集合 \(X\) が生成する部分空間を \(\mathrm{span}(X)\) で表します。

\(\bm{b}\) が \(X\) の要素の線形結合で表される \(\Leftrightarrow \bm{b} \in \mathrm{span}(X)\) であることを用いると、整数 \(A_i, X_i\) に対応するベクトルを \(\bm{a}_i, \bm{x}_i\) と表すとき、

\(A_{L_i}, \dots, A_{R_i}\) からいくつか選んで \(\mathrm{xor}\) を \(X_i\) にできる
\(\Leftrightarrow \bm{x}_i \in \mathrm{span}(\{\bm{a}_k, \bm{a}_{k + 1}, \dots, \bm{a}_{R_i} \})\) となるような \(k\) が存在し、かつそのような \(k\) の最大値が \(L_i\) 以上である

と言い換えられます。

ここで、\(1 \leq i \leq N\) に対し、\(\mathrm{span}(\{\bm{a}_k, \bm{a}_{k + 1}, \dots, \bm{a}_{i} \}) \neq \mathrm{span}(\{\bm{a}_{k + 1}, \dots, \bm{a}_{i}\})\) となるような \(1\) 以上 \(i\) 以下の整数 \(k\) の集合を \(K_i\) とおくと、次が成り立ちます。

• \(\{ \bm{a}_k \, | \, k \in K_i \}\) は \(\mathrm{span}(\{\bm{a}_{1}, \bm{a}_{2},\dots, \bm{a}_{i}\})\) の基底
• \(\mathrm{span}(\{\bm{a}_{l}, \dots, \bm{a}_{r}\}) = \mathrm{span}(\{\bm{a}_k \, | \, k \in K_r \land k \geq l \})\)

以下では、ベクトル \(\bm{b} \in \mathrm{span}(\{ \bm{a}_k \, | \, k \in K_{i} \})\) を \(\{ \bm{a}_k \, | \, k \in K_{i} \}\) の要素の線形結合で（一意に）表したとき、係数が \(0\) でないベクトルの集合を \(\mathrm{nonzero} (\bm{b}, i)\) で表すことにします。\(i\) 番目のクエリにおいて \(\{ \bm{a}_k \, | \, k \in K_{R_i} \}\) に含まれないベクトルを考慮する必要はないため、クエリの答えが Yes であるための必要十分条件は、\(\bm{x}_i \in \mathrm{span}(\{ \bm{a}_k \, | \, k \in K_{R_i} \})\) であり、かつ \(\mathrm{nonzero} (\bm{x}_i, R_i)\) に含まれるベクトルに対応する添字の最小値が \(L_i\) 以上であることです。

\(i\) を \(1\) から順に増やしていったとき、\(K_i\) は次のように変化します。

• \(\bm{a}_{i + 1} \notin \mathrm{span}(\{\bm{a}_{1}, \dots, \bm{a}_{i}\})\) のとき
  • \(K_{i + 1} = K_i \cup \{ i+ 1\}\) となります。
• \(\bm{a}_{i + 1} \in \mathrm{span}(\{\bm{a}_{1}, \dots, \bm{a}_{i}\})\) のとき
  • \(K_i\) の要素を昇順に並べたものを \(k_1, \dots, k_m\) とおきます。\(\mathrm{nonzero}(\bm{a}_{i + 1}, i)\) に含まれるベクトルに対応する添字の最小値が \(k_t\) であるとします。このとき、\(t = j\) ならば \(\mathrm{span}(\{ \bm{a}_{k_j}, \dots, \bm{a}_{k_m}, \bm{a}_{i + 1} \}) = \mathrm{span}(\{ \bm{a}_{k_{j + 1}}, \dots, \bm{a}_{k_m}, \bm{a}_{i + 1} \})\) であり、\(t \neq j\) ならば \(\mathrm{span}(\{ \bm{a}_{k_j}, \dots, \bm{a}_{k_m}, \bm{a}_{i + 1} \}) \neq \mathrm{span}(\{ \bm{a}_{k_{j + 1}}, \dots, \bm{a}_{k_m}, \bm{a}_{i + 1} \})\) となります。よって、\(K_{i + 1} = (K_i \setminus \{k_t\}) \cup \{i + 1\}\) とすればよいです。

さて、\(K_i\) の更新とクエリの処理において、以下の問題を解く必要があります。

• 与えられたベクトル \(\bm{b}\) を \(\{ \bm{a}_k \, | \, k \in K_{i} \}\) の要素の線形結合で表すことができるか判定し、できるならば表し方を求める。

これは、以下の条件を満たすような \(\mathrm{span}(\{ \bm{a}_k \, | \, k \in K_{i} \})\) の基底 \(\bm{b}_1, \dots, \bm{b}_{|K_i|}\) を管理することで高速に行うことができます。

• \(\bm{b}_i\) の第 \(j\) 成分を \(b_{i, j}\) で表したとき、\(m_i = \min \{ j \, | \, b_{i, j} \neq 0 \}\) とおくと、\(i \neq j\) ならば \(b_{j, m_i} = 0\) である。

行列の掃き出し法のような処理を行うことで \(\{ \bm{a}_k \, | \, k \in K_{i} \}\) から \(\bm{b}_1, \dots, \bm{b}_{|K_i|}\) を得ることができます。この際に、各 \(b_i\) がどのように \(\{ \bm{a}_k \, | \, k \in K_{i} \}\) の要素の線形結合によって表されるか管理しておくことで、与えられたベクトル \(\bm{b}\) を \(\bm{b}_1, \dots, \bm{b}_{|K_i|}\) の線形結合で表す方法から、\(\{ \bm{a}_k \, | \, k \in K_{i} \}\) の要素の線形結合で表す方法を復元することができます。

\(S_j = \mathrm{nonzero}(\bm{b}_j, i)\) とおきます。
\(K_i\) を更新するとき、\(\bm{b}_1, \dots, \bm{b}_{|K_i|}\) および \(S_1, \dots, S_{|K_i|}\) は次のように更新します。

• \(K_{i + 1} = K_i \cup \{ i+ 1\}\) となるとき
  • \(\bm{b}_1, \dots, \bm{b}_{|K_i|}\) を用いて \(\bm{a}_{i + 1}\) を掃き出すことによって、全ての \(1 \leq j \leq |K_i|\) に対し第 \(m_j\) 成分が \(0\) であるようなベクトル \(\bm{b'}\) と、\(\mathrm{nonzero}(\bm{b'}, i + 1)\)（これを \(S'\) とおく）が得られます。\(\bm{b'}\) の最初の非零成分が第 \(s\) 成分であるとしたとき、\(b_{j, s} \neq 0\) であるような \(j\) に対し \(\bm{b}_j\) を \(\bm{b}_j + \bm{b'}\) で、\(S_j\) を \(S_j \oplus S' \) で更新します。この処理の後、\(\bm{b}', S'\) をそれぞれ \(\bm{b}_1, \dots, \bm{b}_{|K_i|}\) と \(S_1, \dots, S_{|K_i|}\) に追加します。
• \(K_{i + 1} = (K_i \setminus \{k_t\}) \cup \{i + 1\}\) となるとき
  • \(\bm{b}_1, \dots, \bm{b}_{|K_i|}\) を用いて \(\bm{a}_{i + 1}\) を掃き出すことによって、\(\mathrm{nonzero}(\bm{a}_{i + 1}, i)\)（これを \(S'\) とおく）が得られます。\(\mathrm{span} (\{ \bm{a}_k \, | \, k \in K_{i} \})\) は変化しないので、\(\bm{b}_j\) を更新する必要はありません。\(k_t\) の定め方により \(\bm{a}_{k_t} \in S'\) であるため、\(\mathrm{nonzero}(\bm{a}_{k_t}, i + 1) = (S' \setminus \{ \bm{a}_{k_t} \}) \cup \{ \bm{a}_{i + 1} \}\) です。\(\bm{a}_{k_t} \in S_j\) であるならば、\(S_j\) を \((S_j \oplus S') \cup \{ \bm{a}_{i + 1} \}\) で置き換えます。

\(K_i\) の要素数は \(\mathrm{span}(\{ \bm{a}_1, \dots, \bm{a}_N \})\) の次元で抑えられるため、この問題を \(O((N + Q) \log (\max A_i))\) で解くことができました。