A7462 | 双重冠军
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
在一场大型竞技活动中，有一个由选手组成的排行榜，排列成一个 $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 |
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？