本問題のテーマは、セグメント木構築時の座標圧縮です。

遅延セグメント木の設計

まず、問題に示されたクエリは遅延セグメント木で処理できることを確認します。

• 文字列 \(S\) に対して、 \(f(S)\) を次の \(2\) つの値の組 \((c _ 0, c _ 1)\) とする。
  • \(c _ 0\) : \(S\) に含まれる 0 の個数
  • \(c _ 1\) : \(S\) に含まれる 1 の個数
• 文字列 \(S\) に対しての作用を、整数 \(g\in \lbrace 0,1 \rbrace\) で表す。\(g=0\) のときは何もしない作用、 \(g=1\) のときは 0 , 1 を反転する作用を表す。
  • 作用 \(x,y\) の合成 \(x \circ y\) は、 \((x + y)\bmod 2\) で表せる。

座標圧縮

本問題では、長さ \(10^{18}\) という非常に長い列（文字列）を扱います。ここまでの問題では、列 \(A = (A _ 1, A _ 2, \ldots ,A _ N)\) に対して \(f((A _ 1)), f((A _ 2)), \ldots ,f((A _ N))\) を計算してセグメント木の末端に配置していましたが、本問題ではこれはできません。

代わりに、すでに一部連結された状態の列に対応する値をセグメント木の末端に配置します。具体的には、すべてのクエリで指定される区間の境界を先に列挙し、隣り合う境界の間の部分に対して \(1\) つの値を計算します。

以上により、本問題を計算量 \(O(Q \log Q)\) で解くことができます。

解答例

• Nachia, C++