题目背景
译自 ROI 2018 Day1 T1. Добыча радия (Extraction of radium)。
题目描述
给一个 n×m 的矩阵 a,矩阵中的数互不相同。
接下来有 q 次修改,每次修改会将某个值修改为一个更大的值。保证修改后矩阵中的数仍互不相同。
每次修改后,请求出:矩阵中有多少个数,既是它所在行的最大值,又是它所在列的最大值。
输入格式
第一行三个整数 n,m,q ,表示矩阵的大小与修改操作的次数。
接下来 n 行,每行 m 个整数,表示该矩阵。
接下来 q 行,每行三个整数 x,y,t,表示将该矩阵第 x 行,第 y 列的元素改为 t。
输出格式
q 行,每行一个整数,表示每次修改后,矩阵中有多少个数满足条件。
提示
对于所有数据,1≤a(i,j)≤107,1≤t≤107,1≤n,m,q≤2×105。
子任务编号 |
n,m |
q |
1 |
1≤n×m≤100 |
1≤q≤100 |
2 |
1≤n×m≤5000 |
1≤q≤5000 |
3 |
1≤n,m≤400 |
1≤q≤2×105 |
4 |
1≤n×m≤2×105 |