Xor Sum 2 [AtCoder Regular Contest 098 D]

https://beta.atcoder.jp/contests/arc098/tasks/arc098_b

解法

https://beta.atcoder.jp/contests/arc098/submissions/2571720

全ての連続部分列のうち、条件を満たすものが何通りあるかという問題によくある方針がある。
「連続部分列の左側を全探索し、右端のなかで最も右にあるものを高速に求める」
　
左端をlとして固定した場合にxor和と総和が等しくなるrを考えてみる。
[l,l]は満たされる。
[l,l+1], [l,l+2], …と考えていくが、ある段階で満たされなくなる。
ある境界でそれが変わるので、二分探索でそれを高速に求めよう。
xor和と総和は累積和をつかって高速に取得できるようにしておこう。
これで右端が高速に求まったので、個数を足していくと答えが得られる。

int N, A[201010];
ll xo[201010], sm[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
 
    rep(i, 0, N) xo[i] = sm[i] = A[i];
    rep(i, 1, N) xo[i] ^= xo[i - 1];
    rep(i, 1, N) sm[i] += sm[i - 1];
 
    ll ans = 0;
    rep(l, 0, N) {
        int ok = l, ng = N;
        while (ok + 1 != ng) {
            int md = (ok + ng) / 2;
 
            ll x = xo[md];
            if (l) x ^= xo[l - 1];
 
            ll s = sm[md];
            if (l) s -= sm[l - 1];
 
            if (x == s) ok = md;
            else ng = md;
        }
 
        ans += ok - l + 1;
    }
    cout << ans << endl;
}