F - Max Matrix Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

長さ N の数列 a と、長さ M の数列 b があります。最初、a,b の要素は全て 0 です。
Q 個のクエリを処理してください。i 個目のクエリでは 3 つの整数 T_i, X_i, Y_i が与えられ、以下の処理をします。

  • T_i = 1 のとき : a_{X_i} を Y_i に置き換える
  • 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 は 1 または 2
  • T_i = 1 ならば 1 \le X_i \le N
  • 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

上から i 行目、左から j 列目に \max(a_i, b_j) を書き込んだマス目は、4 回のクエリで以下のように変化します。

入力例 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 bit 整数型に収まらない可能性があります。

Score : 600 points

Problem Statement

We have a sequence a of length N and a sequence b of length M. Initially, every element in a and b is 0.
You are asked to process Q queries. In the i-th query, given three integers T_i, X_i, and Y_i, do the following:

  • if T_i = 1: replace a_{X_i} with Y_i;
  • if T_i = 2: replace b_{X_i} with Y_i.

Then, after processing each query, print the value \displaystyle \sum_{i = 1}^N \sum_{j = 1}^M \max(a_i, b_j).

Constraints

  • 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
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print Q integers as instructed in Problem Statement, with newline as separator.

Sample Input 1

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

Sample Output 1

20
50
55
85

If we write \max(a_i, b_j) at the i-th row and j-th column in a grid, the four queries will change it as follows:

Sample Input 2

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

Sample Output 2

30
44
31
56
42

Sample Input 3

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

Sample Output 3

20000000000000
39999900000000
59999800000000
59999800000000

The integers to be printed may not fit into a 32-bit integer type.