This article uses many terms of linear algebra. Also, the 1-based indexing in the problem statement is translated to the 0-based one.

An integer between \(0\) (inclusive) and \(2^{60}\) can be considered as an element of a vector space \({\mathbb{F}_2}^{60}\), and the exclusive logical sum \(\operatorname{xor}\) as the addition on the space.

Noting that \(\mathbb{F}_2=\lbrace0,1\rbrace\), the \(\operatorname{xor}\) of one or more positive integers chosen from \(A=(A _ 0,\ldots,A _ {N-1})\) can be represented by \(\displaystyle\sum _ {i=0} ^ {N-1}c _ i\bm{a} _ i\), a linear combination of the sequence \((\bm{a} _ i) _ {0\leq i\lt N}\) of vectors that corresponds to the elements of \(A\). Conversely, a vector that is represented by such a linear combination corresponds to the \(\operatorname{xor}\) of one or more vectors chosen from the original sequence.

Therefore, once we obtain the basis \((\bm{e} _ i) _ {0\leq i\lt x}\) of the subspace of \({\mathbb{F}_2}^{60}\) spanned by \((\bm{a} _ i) _ {0\leq i\lt N}\), we can obtain the expression that corresponds one-by-one to the \(\operatorname{xor}\).

Especially, one can take a basis that looks like:

\[ \left\lparen\begin{matrix}\bm e _ 0\\\vdots\\\bm e _ i\\\vdots\\\bm e _ {x-1}\end{matrix}\right\rparen=\left\lparen\ \begin{matrix}0&\cdots&0&0&\cdots&0&0&0&\cdots&0&1&\ast&\cdots&\ast\\\vdots&\ddots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\0&\cdots&0&0&\cdots&0&1&\ast&\cdots&\ast&0&\ast&\cdots&\ast\\\vdots&\ddots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\0&\cdots&1&\ast&\cdots&\ast&0&\ast&\cdots&\ast&0&\ast&\cdots&\ast\end{matrix}\ \right\rparen \]

In terms of integers, the basis satisfies the following two conditions:

• \(e _ 0\lt e _ 1\lt\cdots\lt e _ {x-1}\);
• If \(i\neq j\), then the \(b\)-th significant bit of \(e _ j\) is \(0\), where the \(\operatorname{msb}\) (most significant bit) of \(e _ i\) is the \(b\operatorname{bit}\)-th one.

Such a basis can be constructed by tweaking the algorithm of constructing noshi’s basis.

Once we obtained such a basis, the vector \(\bm s _ i\) that corresponds to the \(i\)-th smallest value \(s _ i\) of total \(\operatorname{xor}\) can be represented as \(\displaystyle\bm s _ i=\sum_{b=0}^{x-1}c _ i\bm e _ i\), where \(c_i\) is the binary notation of \(i\), that is, \(\displaystyle i=\sum _ {b=0} ^ {x-1}c _ i2 ^ i\ (c _ i=0,1)\).

Therefore, given some \(X\), the value of \(s _ X\) can be obtained in an \(O(x)\) time, where \(x\) is the size of the basis.

Given a length-\(N\) sequence of positive integers (that fit in the word size), finding the basis can be found in an \(O(Nx)\) time; together with sorting the basis in ascending order, the problem can be solved in a total of \(O((N+(R-L))x)\) time. Since \(x\) is the size of the basis of a subspace of \({\mathbb{F}_2}^{60}\), we have \(0\leq x\leq 60\), so it is fast enough.

One can modify the form of the basis to solve it in a total of \(O(Nx+(R-L))\) time.

The following is a sample code.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    using namespace std;

    int N;
    cin >> N;
    unsigned long L, R;
    cin >> L >> R;
    --L;
    --R;

    // Construct the basis
    vector<unsigned long> basis;
    for (int i = 0; i < N; ++i) {
        unsigned long A;
        cin >> A;
        for (auto b : basis)
            if ((A ^ b) < A)
                A ^= b;
        for (auto &&b : basis)
            if ((A ^ b) < b)
                b ^= A;
        if (A)
            basis.emplace_back(A);
    }

    // sort in ascending order
    sort(begin(basis), end(basis));

    // Obtain the L-th value
    unsigned long ans{};
    for (int i = 0; i < 60; ++i)
        if (L >> i & 1)
            ans ^= basis[i];

    for (int i = 1; i < size(basis); ++i)
        basis[i] ^= basis[i - 1];

    // Print the L-th through R-th values
    cout << ans;
    for (unsigned long x{L}; x < R; ++x) {
        ans ^= basis[__builtin_popcountl(x ^ (x + 1)) - 1]; // Update the difference
        cout << " " << ans;
    }
    cout << endl;

    return 0;
}