A7462. 双重冠军
编程题
普及/提高-
知识点
题目描述
在一场大型竞技活动中,有一个由选手组成的排行榜,排列成一个 $n \times m$ 的网格。每个位置代表一位选手的成绩,且所有成绩互不相同。
给定一个 $n \times m$ 的整数矩阵 $a$,其中每个元素表示对应选手的成绩,且矩阵中所有数值均不相同。
接下来会进行 $q$ 次操作。每次操作会将某个位置的成绩**直接修改为一个更大的新成绩**(注意:不是在原值上增加,而是替换为一个更大的数)。保证每次修改后,矩阵中的所有数仍然互不相同。
在每次修改完成后,你需要统计当前矩阵中满足以下条件的元素个数:
- 该元素是其所在**行的最大值**;
- 同时也是其所在**列的最大值**。
这样的元素称为“**双重冠军**”。
请在每次修改后输出当前“双重冠军”的数量。
给定一个 $n \times m$ 的整数矩阵 $a$,其中每个元素表示对应选手的成绩,且矩阵中所有数值均不相同。
接下来会进行 $q$ 次操作。每次操作会将某个位置的成绩**直接修改为一个更大的新成绩**(注意:不是在原值上增加,而是替换为一个更大的数)。保证每次修改后,矩阵中的所有数仍然互不相同。
在每次修改完成后,你需要统计当前矩阵中满足以下条件的元素个数:
- 该元素是其所在**行的最大值**;
- 同时也是其所在**列的最大值**。
这样的元素称为“**双重冠军**”。
请在每次修改后输出当前“双重冠军”的数量。
输入格式
- 第一行包含三个整数 $n, m, q$,分别表示矩阵的行数、列数以及操作次数。
- 接下来 $n$ 行,每行包含 $m$ 个整数,表示初始矩阵。
- 接下来 $q$ 行,每行包含三个整数 $x, y, t$,表示将第 $x$ 行、第 $y$ 列的元素修改为 $t$。
- 接下来 $n$ 行,每行包含 $m$ 个整数,表示初始矩阵。
- 接下来 $q$ 行,每行包含三个整数 $x, y, t$,表示将第 $x$ 行、第 $y$ 列的元素修改为 $t$。
输出格式
输出 $q$ 行,每行一个整数,表示每次修改后“双重冠军”的数量。
输入输出样例
输入 #1
2 3 3 1 4 3 6 5 2 2 2 9 1 3 5 2 2 10
输出 #1
1 2 2
说明/提示
对于所有数据:
- $1 \le a_{i,j} \le 10^7$
- $1 \le t \le 10^7$
| 子任务编号 | 范围限制 | 分值 |
|------------|----------|------|
| 1 | $1 \le n \times m \le 100$, $1 \le q \le 100$ | 25 |
| 2 | $1 \le n \times m \le 5000$, $1 \le q \le 5000$ | 25 |
| 3 | $1 \le n, m \le 400$, $1 \le q \le 2 \times 10^5$ | 25 |
| 4 | $1 \le n \times m \le 2 \times 10^5$, $1 \le q \le 2 \times 10^5$ | 25 |
- $1 \le a_{i,j} \le 10^7$
- $1 \le t \le 10^7$
| 子任务编号 | 范围限制 | 分值 |
|------------|----------|------|
| 1 | $1 \le n \times m \le 100$, $1 \le q \le 100$ | 25 |
| 2 | $1 \le n \times m \le 5000$, $1 \le q \le 5000$ | 25 |
| 3 | $1 \le n, m \le 400$, $1 \le q \le 2 \times 10^5$ | 25 |
| 4 | $1 \le n \times m \le 2 \times 10^5$, $1 \le q \le 2 \times 10^5$ | 25 |