【C++】配列の指定範囲に偶数回出現する要素のXORを効率的に求める方法

この記事では、n個の要素からなる配列と、配列上の開始位置Lから終了位置Rまでを指定する複数のクエリが与えられたとき、各範囲内に偶数回出現した要素のXORを求める問題をC++で解きます。

問題の例

まず、具体的な入力と出力を見てみましょう。

入力:

array = {1, 2, 3, 1, 1, 2, 2, 3}
queries = 2
L = 2, R = 5
L = 2, R = 7

出力:

1
0

範囲[2, 5]には {3, 1, 1, 2} が含まれ、「1」だけが2回(偶数回)出現するため答えは1になります。一方、範囲[2, 7]には {3, 1, 1, 2, 2, 3} が含まれ、すべての値が偶数回出現するため、答えは 3 ^ 1 ^ 2 = 0 となります。

解法の考え方

この問題は、XORの性質を利用すると効率的に解くことができます。ポイントは次の2つです。

• 範囲内の全要素のXORを計算すると、奇数回出現した値だけが残ります(偶数回出現する値は自分自身とのXORで打ち消し合うため)。
• そこに、範囲内に存在する異なる値をそれぞれ1回だけXORした値をさらに組み合わせると、今度は偶数回出現した値だけが残ります。

つまり、答えは次の式で表せます。

答え = (範囲内の全要素のXOR) XOR (範囲内の異なる値のXOR)

「範囲内の全要素のXOR」は、プレフィックスXOR(累積XOR)を事前計算しておけばO(1)で求められます。「範囲内の異なる値のXOR」は、各値の最後の出現位置だけをBIT(Binary Indexed Tree / フェニック木)に登録することで求めます。クエリを右端Rの昇順にソートしてオフライン処理することで、すべてのクエリを効率よく捌けます。

C++での実装例

上記のアイデアを実装したプログラムがこちらです。

#include <bits/stdc++.h>
using namespace std;
struct que {
    int L, R, idx;
};
bool cmp(que a, que b){
    if (a.R != b.R)
        return a.R < b.R;
    else
        return a.L < b.L;
}
int findXORSum(int BIT[], int index){
    int xorSum = 0;
    index = index + 1;
    while (index > 0){
        xorSum ^= BIT[index];
        index -= index & (-index);
    }
    return xorSum;
}
void updateBIT(int BIT[], int N, int index, int val){
    index = index + 1;
    while (index <= N){
        BIT[index] ^= val;
        index += index & (-index);
    }
}
int* createBitTree(int arr[], int N){
    int* BIT = new int[N + 1];
    for (int i = 1; i <= N; i++)
        BIT[i] = 0;
    return BIT;
}
void findXORSolution(int arr[], int N, que queries[], int Q, int BIT[]){
    int* prefixXOR = new int[N + 1];
    map<int, int> XORval;
    for (int i = 0; i < N; i++) {
        if (!XORval[arr[i]])
            XORval[arr[i]] = i;
        if (i == 0)
            prefixXOR[i] = arr[i];
        else
            prefixXOR[i] = prefixXOR[i - 1] ^ arr[i];
    }
    int lastOcc[1000001];
    memset(lastOcc, -1, sizeof(lastOcc));
    sort(queries, queries + Q, cmp);
    int res[Q];
    int j = 0;
    for (int i = 0; i < Q; i++){
        while (j <= queries[i].R){
            if (lastOcc[XORval[arr[j]]] != -1)
                updateBIT(BIT, N, lastOcc[XORval[arr[j]]], arr[j]);
            updateBIT(BIT, N, j, arr[j]);
            lastOcc[XORval[arr[j]]] = j;
            j++;
        }
        int allXOR = prefixXOR[queries[i].R] ^ prefixXOR[queries[i].L - 1];
        int distinctXOR = findXORSum(BIT, queries[i].R) ^ findXORSum(BIT, queries[i].L - 1);
        res[queries[i].idx] = allXOR ^ distinctXOR;
    }
    for (int i = 0; i < Q; i++)
        cout << res[i] << endl;
}
int main() {
    int arr[] = {1, 2, 1, 1, 2, 2, 3, 1, 3};
    int N = sizeof(arr) / sizeof(arr[0]);
    int* BIT = createBitTree(arr, N);
    que queries[4];
    queries[0].L = 1;
    queries[0].R = 4; queries[0].idx = 0;
    queries[1].L = 2;
    queries[1].R = 7, queries[1].idx = 1;
    queries[2].L = 0;
    queries[2].R = 3, queries[2].idx = 2;
    queries[3].L = 3;
    queries[3].R = 6, queries[3].idx = 3;
    int Q = sizeof(queries) / sizeof(queries[0]);
    cout<<"Xor sum for all queries is \n";
    findXORSolution(arr, N, queries, Q, BIT);
    return 0;
}

実行結果

Xor sum for all queries is
3
2
0
2

例えば最初のクエリ[1, 4]では、範囲内の要素 {2, 1, 1, 2} のうち「1」と「2」がどちらも2回(偶数回)出現しているため、答えは 2 ^ 1 = 3 となります。

計算量

各要素はBITに対して高々2回更新され、各クエリの処理はO(log N)で完了するため、全体の計算量はO((N + Q) log N)となります。各クエリごとに範囲を毎回走査する素朴なO(N × Q)の手法と比べ、配列サイズやクエリ数が大きい場合でも高速に動作するのが大きな利点です。