题目详情题解（0）讨论（0）提交记录（0）

AT_jsc2021_f.Max Matrix

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个长度为 NN 的数列 aa 和一个长度为 MM 的数列 bb。最初，aa 和 bb 的所有元素均为 00。
请处理 QQ 个查询。对于第 ii 个查询，给出三个整数 Ti, Xi, YiT_i,\ X_i,\ Y_i，进行如下操作：

  • 当 Ti=1T_i = 1 时：将 aXia_{X_i} 替换为 YiY_i。
  • 当 Ti=2T_i = 2 时：将 bXib_{X_i} 替换为 YiY_i。

每次查询操作后，输出 ∑i=1N∑j=1Mmax⁡(ai,bj)\displaystyle \sum_{i=1}^N \sum_{j=1}^M \max(a_i, b_j) 的值。

输入格式

输入以如下格式从标准输入读入。

NN MM QQ
T1T_1 X1X_1 Y1Y_1
T2T_2 X2X_2 Y2Y_2
T3T_3 X3X_3 Y3Y_3
⋮\vdots
TQT_Q XQX_Q YQY_Q

输出格式

按照题目要求，输出 QQ 个整数，每个整数占一行。

输入输出样例

  • 输入#1

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

    输出#1

    20
50
55
85

  • 输入#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

说明/提示

约束

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 1≤Q≤2×1051 \leq Q \leq 2 \times 10^5
  • TiT_i 为 11 或 22
  • 若 Ti=1T_i = 1，则 1≤Xi≤N1 \leq X_i \leq N
  • 若 Ti=2T_i = 2，则 1≤Xi≤M1 \leq X_i \leq M
  • 1≤Yi≤1081 \leq Y_i \leq 10^8
  • 输入中的所有值均为整数

样例解释 1

在每次查询后，将 max⁡(ai,bj)\max(a_i, b_j) 写入第 ii 行第 jj 列的格子中，经过 44 次查询后，格子的变化如下所示。

样例解释 3

输出的整数可能超出 3232 位整数型的范围。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页