XORの性質

XORキャンセル

XORはもう一度同じものをXORすることでキャンセルをすることができる

XORも累積和と同じように累積を取りことができる

XORキャンセルを使って累積の部分のXORを計算できる

この場合全ての要素についてそれぞれの桁についてbitが立っているのは一個だけであるのが確定するので、その範囲内では部分列も同じことが成り立つ