ARC098 D Xor Sum2(500)
問題概要
長さNの数列で、1 <= l <= r <= Nで、[l, r]の区間において、すべての要素のxorと和が等しい(l, r)の組の数を数え上げよ。
N <= 2 * 10^5 数列の中身 < 2^20
ACするまで
1.満たすべき条件は、実は区間内において、2進数の各桁で1がたかだか1つしか現れない と同値
2.各桁ごとに見ようと思ったけど、各桁の許容区間の統合がすごくめんどくさそう つらい。
3.よく見てみると、ある条件を満たすすべての区間内の連続部分列もまた条件を満たす。 -> しゃくとり法
考察
しゃくとり法の大原則として、条件を満たす区間の端は単調にしか変化しない！である。
これをもっと言い換えてみると、区間の左端を固定した時、右端を動かしていくと、ある場所を境に満たすと満たさないが分かれることである。
さらに言えば、条件を満たす区間の連続部分列はもまたすべて条件を必ず満たす。
なぜなら、条件を満たさない区間を連続部分列とした区間では、必ず条件を満たしえないためである。
この大原則を適用すると、a xor b + 2 * (a and b) == a + bなので、基本的に a xor b == a + b から a xor b < a + b への一方通行であるので、明らかにしゃくとり法を適用できるとわかる。
あとはしゃくとり法をやるだけでAC。しゃくとり法についてはけんちょんさんの記事を参照すると書きやすい。
日ハム、大砲早く出てきてくれ。
Xor sumシリーズ、全部違う知見をばらまくので好きです。
