P9286 [ROI 2018] Extraction of radium

Translated from [ROI 2018 Day1](https://neerc.ifmo.ru/school/archive/2017-2018.html) T1. [Добыча радия](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day1.pdf) ([Extraction of radium](http://codeforces.com/gym/102147/problem/A)).

You are given an $n \times m$ matrix $a$, and all numbers in the matrix are pairwise distinct. Then there are $q$ updates. Each update changes one value to a larger value. It is guaranteed that after each update, all numbers in the matrix are still pairwise distinct. After each update, compute how many numbers in the matrix are both the maximum in their row and the maximum in their column.

The first line contains three integers $n$, $m$, $q$, representing the size of the matrix and the number of updates. The next $n$ lines each contain $m$ integers, describing the matrix. The next $q$ lines each contain three integers $x$, $y$, $t$, meaning to change the element in row $x$ and column $y$ to $t$.

Output $q$ lines, each containing one integer, representing after each update how many numbers in the matrix satisfy the condition.

Constraints: For all testdata, $1 \leq a(i,j) \leq 10^7$, $1 \leq t \leq 10^7$, $1 \leq n, m, q \leq 2 \times 10^5$. | Subtask ID | $n,m$ | $q$ | | :-----------: | :-----------: | :-----------: | | $1$ | $1 \leq n \times m \leq 100$ | $1 \leq q \leq 100$ | | $2$ | $1 \leq n \times m \leq 5000$ | $1 \leq q \leq 5000$ | | $3$ | $1 \leq n,m \leq 400$ | $1 \leq q \leq 2 \times 10^5$ | | $4$ | $1 \leq n \times m \leq 2 \times 10^5$ | $1 \leq q \leq 2 \times 10^5$ | Translated by ChatGPT 5