実行時間制限: 3 sec / メモリ制限: 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.