B. XOR-pyramid | Codeforces Round #483 (Div. 1)

/**
実験すると各引数が二項係数と同じ個数だけxorに使われることがわかる。例えば
f(1, 2, 4, 8)
= (1)⊕(2⊕2⊕2)⊕(4⊕4⊕4)⊕(8)
であり、各引数はC(3, 0), C(3, 1), C(3, 2), C(3, 3)
回だけ使われている。
xorは同じ整数同士で打ち消し合うので二項係数の偶奇だけわかればいい。
**/

// C[a][b] % mod, a, b <= nを求める
vector<vector<int>> combinations(int n, int mod) {
    auto res = vector<vector<int>>(n + 1, vector<int>(n + 1));
    rep(i, n + 1) res[i][0] = 1;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j)
        res[i][j] = (res[i - 1][j - 1] + res[i - 1][j]) % mod;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    int N;
    cin >> N;
    auto C = combinations(N, 2);

    vi A(N);
    rep(a, N)cin >> A[a];

    // X[l][r]:=f(A[l], A[l+1],..., A[r])
    vector<vi> X(N, vi(N));
    for (int a = 1; a <= N; ++a) { // 長さaの部分文字列
        vi Y;
        rep(b, a) {
            // 奇数だけ拾っていく
            if (C[a - 1][b])Y.push_back(b);
        }
        for (int l = 0; l + a <= N; ++l) {
            int r = l + a;
            int x = 0;
            each(y, Y) {
                // ここで10^9回程度計算する必要があるが2secで
                // なんとか間に合う
                x ^= A[l + y];
            }
            X[l][r - 1] = x;
        }
    }

    // l<=a, b<=rならばクエリ[l, r]に対して[a, b]の値も
    // 見る必要がある。DPで内側のセグメントを伸ばしていく
    for (int len = 1; len <= N; ++len) {
        for (int l = 0; l + len <= N; ++l) {
            int r = l + len - 1;
            if (l > 0)smax(X[l - 1][r], X[l][r]);
            if (r < N - 1)smax(X[l][r + 1], X[l][r]);
        }
    }

    int Q;
    cin >> Q;
    rep(q, Q) {
        int l, r;
        cin >> l >> r;
        cout << X[l - 1][r - 1] << endl;
    }
}