2019-05-15
なるほど、こういうのを「しゃくとり法」というのか。
最初、「累積和か、しってる！」、「Xor の方も同じように累積（排他的論理）和すればいいのね」とかいって、 いそいそと書いたら TLE。 そりゃそうだ。これでは、\(O(N^2)\) っぽいしなぁ。（正確にはちがうか*1）
各二進桁にある 1 の個数が高々 1 個のときにかぎり、Add と Xor の結果が同じになる。 これは、リプルキャリーアダーとかを思い出せばわかる。
で、もうひとつ、(l, r) 区間で条件がなりたつときには、ここに含まれる任意の部分区間でも条件は成立する。 （「高々１」から減る方向なので）
これに気づけば、あとは、「しゃくとり法」で \(O(N)\)