yukicoder - No.879 Range Mod 2 Query
解説
遅延セグ木のノードに(総和、偶数の個数、奇数の個数)を持ちます。
更新クエリは(クエリ1パターン、加算)という風にします。
クエリ1パターンは3通りあって、
- クエリ1パターンがない (実装の0)
- クエリ1パターンがある(偶奇はそのまま) (実装の1)
- クエリ1パターンがある(偶奇が入れ替わってる) (実装の2)
で、偶奇は加算が奇数であるたびに入れ替わることに注意すると以下の実装のようになります。
遅延セグ木のノードに(総和、偶数の個数、奇数の個数)を持ちます。
更新クエリは(クエリ1パターン、加算)という風にします。
クエリ1パターンは3通りあって、
で、偶奇は加算が奇数であるたびに入れ替わることに注意すると以下の実装のようになります。