【C++】区間のXORと総和が一致する(l, r)ペアの個数を二分探索で効率的に求める方法

問題概要

N個の要素を持つ配列Aが与えられます。このとき、次の条件を満たす整数のペア(l, r)の個数を求めてください。

A[l] XOR A[l+1] XOR … XOR A[r] = A[l] + A[l+1] + … + A[r]

つまり、「区間内の要素をXORした結果」と「区間内の要素を足し合わせた結果」が一致するような区間を数え上げる問題です。

例えば、入力が A = [2, 5, 4, 6] の場合、出力は 5 になります。これは、(1,1)、(2,2)、(3,3)、(4,4)、(1,2) の5つのペアが条件を満たすためです。

解法のポイント

すべての(l, r)の組み合わせを素直に調べるとO(N²)の計算量が必要になり、Nが大きい場合は現実的ではありません。そこで、次の2つの性質を利用します。

• 区間の総和は常にXOR以上になる: 加算とXORの違いは「繰り上がりが発生するかどうか」だけです。したがって、任意の区間について 総和 ≥ XOR が常に成り立ちます。
• 条件には単調性がある: 左端lを固定したとき、右端rを伸ばしていって一度「総和 ≠ XOR」になったら、それ以降は二度と等号が成立しません。すでに総和がXORより大きい状態でさらに要素を追加しても、その差は決して埋まりません。

この単調性のおかげで、各lに対して「条件を満たす最大のr」を二分探索で求めることができます。条件を満たすrは連続した範囲になるため、見つかった最大のrに対して (r − l + 1) 個のペアが存在することになり、これを答えに加算していきます。

アルゴリズムの手順

1. 1-indexedの配列aに元の配列Aの値をコピーします。
2. s[i](先頭からi番目までの累積和)と sx[i](先頭からi番目までのXOR累積)を前計算しておきます。これにより、任意の区間の総和とXORをO(1)で取得できます。
3. 各lについて二分探索を行い、s[mi] − s[l−1] と sx[mi] XOR sx[l−1] が一致する最大のmiをrとして求めます。
4. res に (r − l + 1) を加算し、最後に res を返します。

n := size of A
Define some arrays of size (n + 1) each, a, s and sx
for initialize i := 1, when i <= n, update (increase i by 1), do:
    a[i] := A[i - 1]
    s[i] := s[i - 1] + a[i]
    sx[i] := sx[i - 1] XOR a[i]
res := 0
for initialize l := 1, when l <= n, update (increase l by 1), do:
    bg := l, en = n, r = l
    while bg <= en, do:
        mi := (bg + en) / 2
        if s[mi] - s[l - 1] is same as (sx[mi] XOR sx[l - 1]), then:
            r := mi
            bg := mi + 1
        Otherwise
            en := mi - 1
        res := res + (r - l + 1)
return res

C++実装例

それでは、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A){
    int n = A.size();
    vector<int> a(n + 1), s(n + 1), sx(n + 1);
    for (int i = 1; i <= n; i++){
        a[i] = A[i - 1];
        s[i] = s[i - 1] + a[i];
        sx[i] = sx[i - 1] ^ a[i];
    }
    int res = 0;
    for (int l = 1; l <= n; l++){
        int bg = l, en = n, r = l;
        while (bg <= en){
            int mi = (bg + en) / 2;
            if (s[mi] - s[l - 1] == (sx[mi] ^ sx[l - 1])){
                r = mi;
                bg = mi + 1;
            }
            else
                en = mi - 1;
        }
        res += (r - l + 1);
    }
    return res;
}
int main(){
    vector<int> A = { 2, 5, 4, 6 };
    cout << solve(A) << endl;
}

計算量

前計算にO(N)、各lに対する二分探索にO(log N)かかるため、全体の時間計算量は O(N log N) です。空間計算量は累積配列の分の O(N) となります。素朴なO(N²)の全探索と比べて大幅に高速化できていることが分かります。

入力

{ 2, 5, 4, 6 }

出力

5