1. 動的セグ木を用いた解法

\(N\)の制約が \(1\leq N\leq2×10^5\) とかの場合は遅延セグメント木の典型問題です。（黒マスを0、白マスを1で表した数列を管理。区間更新と区間和取得ができるようにする）

セグメント木のサイズが大きすぎる場合、必要なところだけ作るセグ木、またの名をDynamic Segment Tree (動的セグメント木)を用いて解きます。

ライブラリさえあればatcoder::lazy_segtreeと同様に扱えます。時間計算量は通常のセグ木なら\(O(N+QlogN)\)ですが、動的セグ木なら\(O(QlogN)\)となりこの問題において高速です。ただし空間計算量にもlogが付き、実行時間の定数倍もかなり悪いです。

実装例(C++) (720ms)

補足

実装例に貼られたセグ木構造体はmaspyさんのライブラリを参考にした筆者のライブラリです。atcoder::lazy_segtreeとはmapping（弊ライブラリにおけるg）、composition（弊ライブラリにおけるh）の引数の順序が異なります。使用の際は注意してください。（Nyaan’s Library上のセグ木たちに共通する設計に一致させています）

あと、大半の動的セグ木ライブラリでは各要素の初期状態が全部単位元です。よってこの問題をそのまま解けるものを持っている参加者は限られそうです。

2. 座標圧縮 + セグ木を用いた解法

「その動的セグ木、本当に必要ですか？」

クエリ先読みができるとき、動的セグ木を使わずとも座標圧縮 + セグ木でできる場合が多いです（この考察の流れは頻繁に出会います）。

定数倍が良いこと、ACL以外のライブラリが不要であること、慣れた実装方法しか扱わなくて済むことなどがこの解法の強みです。

\(L,R\)を先読みして半開区間にして、その全部の要素を圧縮します。あと\(0\)と\(N\)も忘れずに入れます（1-indexedの場合は\(1\)と\(N+1\)）。こうすることで圧縮後の各区間が白マスのみまたは黒マスのみであり続けることが保証されます。

あとは各区間の白マスの数を管理すればOKです。\(O(QlogQ)\)。

実装例(C++) (257ms)

個人的には座圧 + セグ木で解いた参加者が多数派ではないことが不自然です。公式解説のような解法は『区間をsetで管理するテク』と呼ばれ、（ライブラリなしであれば）実装の重さに定評があります。