Покраска

Будем для каждого значения $$$t$$$ от $$$1$$$ до $$$n + 1$$$ поддерживать, сколько клеток нужно перекрасить, чтобы все клетки до $$$t$$$-го ряда (не включая его) имели черный цвет, а после него — белый цвет. Для изначальной конфигурации эти значения легко посчитать за линейное время от размера поля (для каждого $$$t$$$ искомая стоимость — это сумма количества клеток белого цвета до $$$t$$$-го ряда и количества клеток черного цвета после $$$t$$$-го ряда). Также будем хранить в массиве все цвета клеток.

Когда поступает запрос на изменение цвета клетки $$$(a, b)$$$, посмотрим, какого цвета была эта клетка. Пусть она была черного цвета. Посмотрим, как изменятся значения, которые мы храним для каждого $$$t$$$. Легко заметить, что все значения до $$$a$$$-го включительно уменьшатся на $$$1$$$, а все значения после него увеличатся на $$$1$$$. Аналогично, если клетка перекрашивается из белого в черный цвет, то все значения до $$$a$$$-го включительно увеличатся на $$$1$$$, а после $$$a$$$-го уменьшатся на $$$1$$$. Также после каждого запросы искомый ответ — это минимальное из значений, которые мы храним. Значит, нам нужно уметь прибавлять ко всем значениям на отрезке фиксированное число и брать минимальное среди всех значений. Для этих операций можно хранить значения в дереве отрезков на минимум с массовыми обновлениями.

Асимптотика времени работы решения составляет $$$\mathcal{O}(nm + q \log n)$$$.