D: Xor Sum 2 - AtCoder Regular Contest 098

排他的論理和が総和以下っぽい。詳しく説明する。

とする。 まずが成り立つ。更にも成り立つ。

部分文字列の左端lを固定してみる。このときr=lならば明らかに条件を満たす。

A[l]⊕A[l+1]⊕...⊕A[r] < A[l]+A[l+1]+...+A[r]

が成り立つと仮定する。このとき、先のxorの性質により

A[l]⊕A[l+1]⊕...⊕A[r]⊕A[r+1] < A[l]+A[l+1]+...+A[r]+A[r+1]

が成り立つ。 よって右端をいくら伸ばしても常に総和のほうが大きい。 つまりl<=r<=Nについて順に

等しい、等しい、等しい、等しい、総和のほうが大きい、総和のほうが大きい

のように等しい場合は左側に、値が異なる場合は右側に寄るので、値が等しくなる場合を二分探索する。

実行時間はO(Nlog(N))

int N;
cin >> N;
vector<ll> S(N + 1), T(N + 1);
rep(a, N) {
    int b;
    cin >> b;
    S[a + 1] = S[a] ^ b;
    T[a + 1] = T[a] + b;
}
ll re = 0;
rep(l, N) {
    int ok = l + 1, ng = N + 1;
    while (ng - ok > 1) {
        int r = (ok + ng) / 2;
        ll s = S[r] ^ S[l];
        ll t = T[r] - T[l];
        (s == t ? ok : ng) = r;
    }
    re += ok - l;
}
cout << re << endl;