Preface

This editorial uses the terms of linear algebra. If you understand them, you may skip this section.

An integer between \(0\) (inclusive) and \(2^{60}\) (exclusive) can be regarded as a \(60\)-dimensional vector, considering its binary notation.
An operation of computing \(\mathrm{xor}\) (exclusive OR) corresponds to finding the sum of each element in \(\bmod \, 2\), and the operation of choosing some elements from a set of integers and finding their \(\mathrm{xor}\) corresponds to multiplying \(0\) or \(1\) to the vectors and summing them up in \(\bmod \, 2\).
A sum of some multiplications of a scalar and a vector is called a linear combination.

In this editorial, for a set of integer \(X\), \(\mathrm{span}(X)\) denotes a set of all possible \(\mathrm{xor}\) of some elements of \(X\).

Solution

An integer between \(0\) (inclusive) and \(2^{60}\) (exclusive) corresponds to a element of \(60\)-dimensional numerical vector space \({ \mathbb{F}_2}^{60}\), and \(\mathrm{xor}\) of some elements of an integer set correspond to a linear combination of vectors. Hereinafter we denote by \(\mathrm{span}(X)\) the subspace generated by a set of vertex \(X\).

Since \(\bm{b}\) is expressed as a linear combination of elements of \(X\) \(\Leftrightarrow \bm{b} \in \mathrm{span}(X)\), denoting by \(\bm{a}_i\) and \(\bm{x}_i\) the vectors corresponding to \(A_i\) and \(X_i\),

it is possible to choose elements from \(A_{L_i}, \dots, A_{R_i}\) so that their \(\mathrm{xor}\) is \(X_i\)
\(\Leftrightarrow\) There exists \(k\) such that \(\bm{x}_i \in \mathrm{span}(\{\bm{a}_k, \bm{a}_{k + 1}, \dots, \bm{a}_{R_i} \})\), and the maximum value of such \(k\) is greater than or equal to \(L_i\).

Here, for \(1 \leq i \leq N\), denoting by \(K_i\) the set of integers between \(1\) and \(i\) (inclusive) such that \(\mathrm{span}(\{\bm{a}_k, \bm{a}_{k + 1}, \dots, \bm{a}_{i} \}) \neq \mathrm{span}(\{\bm{a}_{k + 1}, \dots, \bm{a}_{i}\})\), the following property holds.

• \(\{ \bm{a}_k \, | \, k \in K_i \}\) is a basis of \(\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 \})\)

Considering the (unique) representation of \(\bm{b} \in \mathrm{span}(\{ \bm{a}_k \, | \, k \in K_{i} \})\) as a linear combination of \(\{ \bm{a}_k \, | \, k \in K_{i} \}\), let us denote by \(\mathrm{nonzero} (\bm{b}, i)\) the set of vectors with non-zero coefficient in it. In the \(i\)-th query, we do not have to consider the vectors that is not included in \(\{ \bm{a}_k \, | \, k \in K_{R_i} \}\), so the answer for the query is Yes if and only if \(\bm{x}_i \in \mathrm{span}(\{ \bm{a}_k \, | \, k \in K_{R_i} \})\) and the minimum index of vectors in \(\mathrm{nonzero} (\bm{x}_i, R_i)\) is greater than or equal to \(L_i\).

As we increment \(i\) from one, \(K_i\) changes as follows.

• If \(\bm{a}_{i + 1} \notin \mathrm{span}(\{\bm{a}_{1}, \dots, \bm{a}_{i}\})\)
  • we can compute as \(K_{i + 1} = K_i \cup \{ i+ 1\}\).
• If \(\bm{a}_{i + 1} \in \mathrm{span}(\{\bm{a}_{1}, \dots, \bm{a}_{i}\})\)
  • Let \(k_1, \dots, k_m\) be the elements of \(K_i\) in the increasing order. Let \(k_t\) be the minimum index of vectors in \(\mathrm{nonzero}(\bm{a}_{i + 1}, i)\). Here, if \(t = j\), then \(\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} \})\), and \(t \neq j\), then \(\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} \})\). Therefore, we can compute as \(K_{i + 1} = (K_i \setminus \{k_t\}) \cup \{i + 1\}\).

Here, when updating \(K_i\) and processing queries, the following problem has to be solved.

• Determine if a given vector \(\bm{b}\) can be expressed as a linear combination of \(\{ \bm{a}_k \, | \, k \in K_{i} \}\), and if possible, find the representation.

This can be processed fast by managing basis of \(\mathrm{span}(\{ \bm{a}_k \, | \, k \in K_{i} \})\), \(\bm{b}_1, \dots, \bm{b}_{|K_i|}\), that satisfies the following conditions:

• Let \(b_{i, j}\) be the \(j\)-th element of \(\bm{b}_i\), and \(m_i = \min \{ j \, | \, b_{i, j} \neq 0 \}\). If \(i \neq j\), then \(b_{j, m_i} = 0\)

By performing Gaussian-elimination-like operations, we can obtain \(\bm{b}_1, \dots, \bm{b}_{|K_i|}\) from \(\{ \bm{a}_k \, | \, k \in K_{i} \}\). Here, by managing how each \(b_i\) is represented as a linear combination of \(\{ \bm{a}_k \, | \, k \in K_{i} \}\), we can recover how to represent the given \(b\) as a linear combination of the elements of \(\{ \bm{a}_k \, | \, k \in K_{i} \}\) from how to represent it as a linear combination of \(\bm{b}_1, \dots, \bm{b}_{|K_i|}\).

Let \(S_j = \mathrm{nonzero}(\bm{b}_j, i)\).
When updating \(K_i\), we update \(\bm{b}_1, \dots, \bm{b}_{|K_i|}\) and \(S_1, \dots, S_{|K_i|}\) as follows.

• If \(K_{i + 1} = K_i \cup \{ i+ 1\}\)
  • By eliminating \(\bm{a}_{i + 1}\) using \(\bm{b}_1, \dots, \bm{b}_{|K_i|}\), we can obtain a vector \(\bm{b'}\) such that the \(m_j\)-th element is \(0\) for all \(1 \leq j \leq |K_i|\), and \(\mathrm{nonzero}(\bm{b'}, i + 1)\) (denoted by \(S'\)). If the first non-zero element of \(\bm{b'}\) is the \(s\)-the element, then for \(j\) such that \(b_{j, s} \neq 0\) we update \(\bm{b}_j\) with \(\bm{b}_j + \bm{b'}\) and \(S_j\) with \(S_j \oplus S' \). After this process, we add \(\bm{b}'\) and \(S'\) to \(\bm{b}_1, \dots, \bm{b}_{|K_i|}\) and \(S_1, \dots, S_{|K_i|}\), respectively.
• If \(K_{i + 1} = (K_i \setminus \{k_t\}) \cup \{i + 1\}\)
  • By eliminating \(\bm{a}_{i + 1}\) using \(\bm{b}_1, \dots, \bm{b}_{|K_i|}\), we obtain \(\mathrm{nonzero}(\bm{a}_{i + 1}, i)\) (denoted by \(S'\)). Since \(\mathrm{span} (\{ \bm{a}_k \, | \, k \in K_{i} \})\) does not change, we do not have to update \(\bm{b}_j\). By the definition of \(k_t\), \(\bm{a}_{k_t} \in S'\) so \(\mathrm{nonzero}(\bm{a}_{k_t}, i + 1) = (S' \setminus \{ \bm{a}_{k_t} \}) \cup \{ \bm{a}_{i + 1} \}\). If \(\bm{a}_{k_t} \in S_j\), then we update \(S_j\) with \((S_j \oplus S') \cup \{ \bm{a}_{i + 1} \}\).

Since the number of elements of \(K_i\) cannot exceed the dimension of \(\mathrm{span}(\{ \bm{a}_1, \dots, \bm{a}_N \})\), so the problem has been solved in a total of \(O((N + Q) \log (\max A_i))\) time.