AtCoder ARC098 D - Xor Sum 2

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

問題概要

整数列A_nが与えられる．区間[l,r]でその区間における総XORと総和とが等しくなるもの(l,rの組）はいくつあるか．

・XORと和との関係で「XORと和が等しい」i.e.「すべてのビットで桁上りを起こさない」i.e.「ビットごとの'1'の個数が1以下」を用いる．今回は20桁以下なので，要素数20の配列で各ビットごとの'1'の個数を管理すればよい．

・もちろん全部の(l,r)の組を試すわけにはいかないが，区間における各ビットごとの'1'の個数は明らかにrに対して単調増加なので，右端が右に行くほどXORにおいて「不利」になる．逆に言えばlに対して単調減少なので左端が右に行くほど「有利」になる．というわけで尺取り法を用いる．

・rを一つ増やしたときに新しく区間に含まれた要素をbitごとに見てbitごとの1の個数を管理する配列に加算していく．次に，lを1ずつ増やして，新たに範囲から外れた要素をbitごとに見てbitごとの1の個数を管理する配列から減算していく．この時，上述の条件が満足されたら，lはそれ以上r以下においてすべて条件を満足するのでr-l+1を答えに加算すればよい．これをr<=N-1でfor文を回して計算すればよい（右端をforで回してよいので若干通常の尺取より脳みそへの負担が軽い気もする）

実装

https://atcoder.jp/contests/arc098/submissions/6657375