この解説では線形代数の言葉を多く使います。 また、問題文中の 1-indexed の値を 0-indexed に読み替えています。

\(0\) 以上 \(2^{60}\) 未満の整数とそのビットごとの排他的論理和 \(\operatorname{xor}\) は、ベクトル空間 \({\mathbb{F}_2}^{60}\) の元とその加法であると考えることができます。

\(\mathbb{F}_2=\lbrace0,1\rbrace\) であることに注意すると、\(A=(A _ 0,\ldots,A _ {N-1})\) から正整数を \(1\) つ以上選んだ総 \(\operatorname{xor}\) は \(A\) の各元に対応するベクトルの列 \((\bm{a} _ i) _ {0\leq i\lt N}\) の線形結合 \(\displaystyle\sum _ {i=0} ^ {N-1}c _ i\bm{a} _ i\) で表されることがわかります。 逆に、このような線型結合で表されるベクトルはもとの列から \(1\) つ以上選んだ総 \(\operatorname{xor}\) と対応しています。

よって、 \((\bm{a} _ i) _ {0\leq i\lt N}\) が張る \({\mathbb{F}_2}^{60}\) の部分空間の基底 \((\bm{e} _ i) _ {0\leq i\lt x}\) をとることができれば、総 \(\operatorname{xor}\) と一対一に対応する表現が得られます。

特に、このような基底をとることができます。

\[ \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 \]

対応する整数の言葉でいうと、次の \(2\) 条件を満たすような基底です。

• \(e _ 0\lt e _ 1\lt\cdots\lt e _ {x-1}\)
• \(e _ i\) の \(\operatorname{msb}\) （\(1\) である最上位ビット） が \(b\operatorname{bit}\) めであるとき、\(i\neq j\) について \(e _ j\) の \(b\operatorname{bit}\) めは \(0\)

このような基底は、いわゆる noshi基底 の構築の際に少し手を加えることで構築できます。

このような基底が取れたとき、総 \(\operatorname{xor}\) のうち小さいほうから \(i\) 番目の値 \(s _ i\) に対応するベクトル \(\bm s _ i\) は、\(i\) の二進法での表記 \(\displaystyle i=\sum _ {b=0} ^ {x-1}c _ i2 ^ i\ (c _ i=0,1)\) について \(\displaystyle\bm s _ i=\sum_{b=0}^{x-1}c _ i\bm e _ i\) と表せます。

よって、適当な \(X\) が与えられたとき \(s _ X\) の値は基底の本数 \(x\) について \(O(x)\) 時間で求められます。

長さ \(N\) の（ワードサイズに収まる）正整数の列に対して、基底をとるのは \(O(Nx)\) 時間で可能なので、基底を昇順にソートするのとあわせて、全体で \(O((N+(R-L))x)\) 時間でこの問題を解くことができます。 \(x\) は \({\mathbb{F}_2}^{60}\) の部分空間の基底の本数なので、\(0\leq x\leq 60\) となり、十分高速です。

基底の形をすこし変えることで、\(O(Nx+(R-L))\) 時間で解くこともできます。

実装例は以下のようになります。

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

int main() {
    using namespace std;

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

    // 基底をつくる
    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(begin(basis), end(basis));

    // L 番目の値を得る
    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];

    // L 番目から R 番目までの値を出力
    cout << ans;
    for (unsigned long x{L}; x < R; ++x) {
        ans ^= basis[__builtin_popcountl(x ^ (x + 1)) - 1]; // 差分を更新
        cout << " " << ans;
    }
    cout << endl;

    return 0;
}