C++で解く「すべての部分配列のXORのXOR」クエリ問題

本記事では、指定された範囲に含まれるすべての部分配列のXORを計算して出力する方法を解説します。

問題の概要

まず、具体的な例を見てみましょう。

入力 : arr[] = { 4, 1, 2, 3, 5 }, Q = 3

クエリ
q1 = { 1, 2 }
q2 = { 2, 4 }
q3 = { 1, 4 }

出力 : 0
2
0

たとえばクエリ2(範囲 2〜4)の場合、対象となる部分配列は以下の通りです。

{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}

ここで各要素の出現回数を数えると、次のようになります。

• 1 は 3 回出現
• 2 は 4 回出現
• 3 は 3 回出現

XORには「偶数回出現する値は打ち消し合う」という重要な性質があります。そのため、4 回出現した 2 は消え、残るのは 3 と 1 のXORのみとなり、これが答えになります。

このように、本問題では数値の出現パターンを観察し、その規則性に基づいて実装を行うことが鍵となります。

解法のアプローチ

この問題を解くポイントは、範囲の長さと要素の出現回数の間に潜むパターンを見抜くことです。パターンを発見できれば、あとはそれに従って効率的な実装を行い、結果を検証します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
void ansQueries(int prefeven[], int prefodd[], int l, int r){
    if ((r - l + 1) % 2 == 0) // 範囲内の要素数が偶数の場合
        cout << "0";
    else{
        if (l % 2 == 0) // l が偶数の場合
            cout << (prefeven[r] ^ prefeven[l - 1]) << "\n";
        else // l が奇数の場合
            cout << (prefodd[r] ^ prefodd[l - 1]) << "\n";
    }
}
int main(){
    int arr[] = {4, 1, 2, 3, 5};
    int n = sizeof(arr) / sizeof(int); // 配列のサイズ
    int l[] = {1, 2, 1}; // 各クエリの左インデックス
    int r[] = {2, 4, 4}; // 各クエリの右インデックス
    int q = sizeof(l) / sizeof(int); // クエリの件数
    int prefodd[n] = {0}, prefeven[n] = {0}; // 偶数・奇数インデックス用のプレフィックスXOR
    for (int i = 1; i <= n; i++){
        if ((i) % 2 == 0){ // i が偶数なら prefeven を更新
            prefeven[i] = arr[i - 1] ^ prefeven[i - 1];
            prefodd[i] = prefodd[i - 1];
        }else{
            prefeven[i] = prefeven[i - 1];
            prefodd[i] = prefodd[i - 1] ^ arr[i - 1];
        }
    }
    for (int i = 0; i < q; i++){
        ansQueries(prefeven, prefodd, l[i], r[i]);
    }
    return 0;
}

実行結果

02
0

コードの解説

このアプローチの核心は、次の2つの観察にあります。

1. 範囲の長さが偶数の場合

範囲内のすべての部分配列を列挙すると、各要素は必ず偶数回出現します。XORの性質により偶数回出現する値はすべて打ち消し合うため、答えは必ず 0 になります。

2. 範囲の長さが奇数の場合

この場合、奇数回出現するのは範囲内の偶数番目の位置にある要素だけです。したがって、答えは「範囲内の偶数位置にある要素のXOR」となります。

これを実現するために、交互の位置のXORを格納する2つのプレフィックス配列を事前に構築します。prefeven には偶数インデックスの要素のXORを、prefodd には奇数インデックスの要素のXORを累積的に記録します。クエリ処理時には、左端 l の偶奇を判定し、対応するプレフィックス配列から pref[r] ^ pref[l-1] を計算するだけで、O(1) で答えを求められます。

まとめ

本記事では、「すべての部分配列のXORのXOR」に対するクエリを効率的に処理する問題を取り上げました。範囲の長さの偶奇による出現回数のパターンを見抜き、偶数・奇数インデックス用の2つのプレフィックスXOR配列を活用することで、各クエリを高速に回答できることを学びました。このアルゴリズムは、C言語やJava、Pythonなど他のプログラミング言語でも同様に実装可能です。皆さんの競技プログラミングや学習の一助となれば幸いです。