Игра с массивом

Заметим, что по каждому биту можно решать задачу независимо, а так как $$${10}^8 < {2}^27$$$, то ненулевыми биты могут быть только младшие $$$27$$$.

Если рассмотреть один бит, задача сводиться к следующей: Есть массив из $$$0$$$ и $$$1$$$, в нём изменяются какие-то элементы, и на подотрезке спрашивают, какое количество подотрезков с нечётным количеством единиц.

Эту информацию можно поддерживать с помощью дерева отрезков. Для того, чтобы "склеить" два отрезка, надо хранить на нём количество подотрезков с нечётным числом единиц, количество префиксов и суффиксов с нечётным числом единиц, длину отрезка и общее количество единиц. Итоговая асимптотика $$$O(m \cdot \log n \cdot \log maxA)$$$.