← 返回题目列表

AtCoder · jsc2021_f

F. 最大矩阵

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一个序列 a 长度 N 和一个序列 b 长度 M。最初,中的每个元素 a 和 b is 0.
您需要处理 Q 查询。在 i-第一个查询,给定三个整数 T_i, X_i,和 Y_i,执行以下操作:

  • if T_i = 1:替换 a_{X_i} 与 Y_i;
  • if T_i = 2:替换 b_{X_i} 与 Y_i.

然后,在处理每个查询后,打印该值 \displaystyle \sum_{i = 1}^N \sum_{j = 1}^M \max(a_i, b_j).

约束

  • 1 \le N \le 2 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le Q \le 2 \times 10^5
  • T_i is 1 or 2.
  • If T_i = 1, 1 \le X_i \le N.
  • If T_i = 2, 1 \le X_i \le M.
  • 1 \le Y_i \le 10^8
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M Q
T_1 X_1 Y_1
T_2 X_2 Y_2
T_3 X_3 Y_3
\hspace{21pt} \vdots
T_Q X_Q Y_Q

输出

打印 Q 整数,如问题陈述中所述,以换行符作为分隔符。


样本输入 1

2 2 4
1 1 10
2 1 20
2 2 5
1 1 30

示例输出 1

20
50
55
85

如果我们写 \max(a_i, b_j) 在 i第行和 j- 网格中的第列,四个查询将对其进行如下更改:


示例输入 2

3 3 5
1 3 10
2 1 7
1 3 5
2 2 10
2 1 1

示例输出 2

30
44
31
56
42

示例输入 3

200000 200000 4
2 112219 100000000
1 73821 100000000
2 26402 100000000
1 73821 100000000

示例输出 3

20000000000000
39999900000000
59999800000000
59999800000000

要打印的整数可能不适合 32位整数类型。