# ARC098 D - Xor Sum 2

2019-05-15

なるほど、こういうのを「しゃくとり法」というのか。

最初、「累積和か、しってる！」、「Xor の方も同じように累積（排他的論理）和すればいいのね」とかいって、
いそいそと書いたら [TLE](https://atcoder.jp/contests/arc098/submissions/5408207)。
そりゃそうだ。これでは、\(O(N^2)\) っぽいしなぁ。（正確にはちがうか$<fn>{違わないね。O(N*(1+N)/2) = O(N) だ}）

各二進桁にある 1 の個数が高々 1 個のときにかぎり、Add と Xor の結果が同じになる。
これは、リプルキャリーアダーとかを思い出せばわかる。

で、もうひとつ、(l, r) 区間で条件がなりたつときには、ここに含まれる任意の部分区間でも条件は成立する。
（「高々１」から減る方向なので）

これに気づけば、あとは、「しゃくとり法」で \(O(N)\) 

提出： [submissions/5408410](https://atcoder.jp/contests/arc098/submissions/5408410)