分数: 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位整数类型。