测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A7462. 双重冠军

编程题 普及/提高-

题目描述

在一场大型竞技活动中,有一个由选手组成的排行榜,排列成一个 $n \times m$ 的网格。每个位置代表一位选手的成绩,且所有成绩互不相同。

给定一个 $n \times m$ 的整数矩阵 $a$,其中每个元素表示对应选手的成绩,且矩阵中所有数值均不相同。

接下来会进行 $q$ 次操作。每次操作会将某个位置的成绩**直接修改为一个更大的新成绩**(注意:不是在原值上增加,而是替换为一个更大的数)。保证每次修改后,矩阵中的所有数仍然互不相同。

在每次修改完成后,你需要统计当前矩阵中满足以下条件的元素个数:

- 该元素是其所在**行的最大值**;
- 同时也是其所在**列的最大值**。

这样的元素称为“**双重冠军**”。

请在每次修改后输出当前“双重冠军”的数量。

输入格式

- 第一行包含三个整数 $n, m, q$,分别表示矩阵的行数、列数以及操作次数。
- 接下来 $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 |
上一题 去做题 下一题