Contest Duration: - (local time) (100 minutes) Back to Home

## 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.

posted:
last update: