Задача №113911. Добыча радия
Поэзия — та же добыча радия.
© Владимир Маяковский
Для геологической разведки перед добычей радия на плато Меридиана на орбиту Марса выведен специальный спутник, позволяющий измерять уровень радиоактивности на поверхности.
Представим плато как прямоугольник, состоящий из n × m единичных квадратов, обозначим j -й квадрат в i -м ряду как ( i , j ) .
В результате сканирования плато для каждого единичного квадрата был определён уровень радиоактивности. Уровень радиоактивности квадрата ( i , j ) задаётся целым положительным числом a ij . Точность измерений настолько велика, что все числа a ij различны. Единичный квадрат ( i , j ) считается подходящим для добычи радия, если значение a ij является максимальным в i -й строке, а также максимальным в j -м столбце.
В процессе наблюдений было проведено q последовательных уточнений уровня радиоактивности. А именно, k -е уточнение изменяло значение a r kc k на некоторое строго большее значение. При этом после каждого уточнения все значения a ij оставались различными.
Требуется написать программу, которая по заданным исходным значениям a ij и списку уточнений после каждого уточнения информации определяет количество подходящих для добычи радия единичных квадратов.
Первая строка входных данных содержит три положительных целых числа: n , m и q ( 1 ≤ n × m ≤ 200 000 , 1 ≤ q ≤ 200 000 ). Обратите внимание, что ограничение сверху дано на площадь плато, а не на количество столбцов и строк по отдельности.
Следующие n строк содержат по m положительных целых чисел, j -е число в i -й из этих строк задаёт начальное значение a ij ( 1 ≤ a ij ≤ 10 7 , все a ij различны).
Следующие q строк описывают уточнения данных, k -я из них содержит три целых числа r k , c k и x k и задаёт изменение информации об уровне радиоактивности единичного квадрата ( r k , c k ) , новое значение равно x k ( 1 ≤ r k ≤ n , 1 ≤ c k ≤ m , 1 ≤ x k ≤ 10 7 ). Гарантируется, что x k строго больше предыдущего уровня радиоактивности в этом квадрате, и что все уровни радиоактивности различны после каждого изменения.
Выходные данные должны содержать q строк, в k -й из этих строк требуется вывести одно число — количество подходящих для добычи радия единичных квадратов после k -го обновления информации.
2 3 3 1 4 3 6 5 2 2 2 9 1 3 5 2 2 10
1 2 2