Vasya and Good Sequences [Codeforces Round #512 (Div. 1, based on Technocup 2019 Elimination Round 1) B]

http://codeforces.com/contest/1053/problem/B

N要素の数列Aがある。
この数列の連続部分列のうち、以下の条件を満たすものが何通りあるか。
　
条件
各要素で、1が立っているビットを自由に動かして数を作ったとき、
その数すべてのXORを取って0にすることができる。

考察過程

1. dpかとも思ったが、重複して数えてしまうのでダメそう
2. 各数について1が立っている数のみ重要となるので、「B[i] := A[i]のビット表記で1が何個立っているか」で考える
3. 条件は「B[i]の総和が偶数」かつ「最大のB[i]≦他のB[i]の総和」っぽい
4. 右端を固定して、条件を満たす左端を数えるいつものやつかと思って実装する
5. 2番目の条件やばくない？
6. 実装終わる気がしない
7. ～終了～
8. コンテスト後のツイッター「後半の条件を満たさないのは、右端から60個ぐらいしかない」
9. わかる

解法

http://codeforces.com/contest/1053/submission/43348808

「右端を固定して、条件を満たす左端を数える」テクを使って数え上げていこう。
　
A[i]の実際の数はあまり問題ではなく、「B[i] := A[i]のビット表記で1が何個立っているか」としたときの数が問題。
今後はこっちで考える。
　
条件の言い換えを考えると「B[i]の総和が偶数」かつ「最大のB[i]≦他のB[i]の総和」が満たされるとき条件が満たされる。
これを高速に数え上げるために累積和とBITを用意しておこう。
sm[i] := B[0] + ... + B[i]
bit[parity](L,R) := sm[L], sm[L+1], ... sm[R-1]の中でmod2したときにparityになる個数
　
後半の条件がやばいように見えるが、この条件が満たされないのは右端より長さが65以下ぐらいの話。
なので、そこだけ探索する。
それ以外は、BITを使って、同じparityの累積和の個数を取ってくる。

int N; ll A[301010]; int B[301010];
int sm[301010];
SparseTable<int> st;
BIT<int> bit[2];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) {
        while (A[i]) {
            if (A[i] & 1) B[i]++;
            A[i] /= 2;
        }
    }

    sm[0] = 0;
    rep(i, 0, N) sm[i + 1] = sm[i] + B[i];

    vector<int> v;
    v.push_back(0);
    rep(i, 0, N) v.push_back(B[i]);
    st.init(v);

    rep(i, 0, 2) bit[i].init(N + 1);
    rep(i, 0, N + 1) bit[sm[i] % 2].add(i, 1);

    ll ans = 0;
    rep(R, 1, N + 1) {
        int L = R - 1; int cnt = 0;
        while (0 <= L and cnt < 65) {
            int ma = st.get(L + 1, R + 1);
            int tot = sm[R] - sm[L];

            if (tot % 2 == 0 and ma <= tot - ma) ans++;
            L--; cnt++;
        }
        ans += bit[sm[R] % 2].get(0, L + 1);
    }
    cout << ans << endl;
}