The theme of this problem is using a segment tree by treating functions as monoid elements.

Designing the monoid

This problem handles \(30\)-bit integers, but each bit is independent. Let us first consider the case of \(1\) bit.

For query 2 l r, each \(A _ i\) (\(l + 1 \leq i \leq r\)) acts as a function \(g _ i\) such that \(g _ i(x) \in \lbrace 0,1 \rbrace\) for \(x \in \lbrace 0,1 \rbrace\). The answer is \(g _ r(\ldots g _ {l+1}( A _ l ) \ldots )\), or, using function composition, \((g _ r \circ \cdots \circ g _ {l+2} \circ g _ {l+1}) (A _ l)\).

A function \(g\) whose domain and codomain are both \(\lbrace 0,1 \rbrace\) can be represented by \(2\) variables holding \(g(0),g(1)\). Two such functions can be composed in \(O(1)\) time. Since function composition is associative, we can treat these functions as a monoid in a segment tree.

In this setting, we can compute function composition using a combination of logical operations. Even when processing \(30\) bits in parallel, bitwise logical operations keep the time complexity at \(O(1)\).

Thus, maintaining function compositions as a monoid in a segment tree gives a solution with time complexity \(O(N + Q \log N)\).

Sample implementation

• Nachia, C++, 57 ms