The theme of this problem is coordinate compression when constructing a segment tree.

Designing the lazy segment tree

First, let us confirm that the queries in the problem can be handled with a lazy segment tree.

• For a string \(S\), define \(f(S)\) as the tuple of \(2\) values \((c _ 0, c _ 1)\):
  • \(c _ 0\): The number of 0s in \(S\).
  • \(c _ 1\): The number of 1s in \(S\).
• Represent an action on a string \(S\) by an integer \(g\in \lbrace 0,1 \rbrace\). The action \(g=0\) does nothing, while \(g=1\) flips 0 and 1.
  • The composition \(x \circ y\) of actions \(x,y\) is represented by \((x + y)\bmod 2\).

Coordinate compression

This problem deals with a very long sequence (string) of length \(10^{18}\). In the previous problems, for a sequence \(A = (A _ 1, A _ 2, \ldots ,A _ N)\), we computed \(f((A _ 1)), f((A _ 2)), \ldots ,f((A _ N))\) and placed them at the leaves of the segment tree. That is not feasible in this problem.

Instead, place values corresponding to sequences that have already been partially concatenated at the leaves of the segment tree. Specifically, enumerate the boundaries of the intervals specified in all queries in advance, and compute \(1\) value for the portion between each pair of adjacent boundaries.

This solves the problem in \(O(Q \log Q)\) time.

Sample implementation

• Nachia, C++