AT_jsc2021_f Max Matrix

[problemUrl]: https://atcoder.jp/contests/jsc2021/tasks/jsc2021_f 長さ $ 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) $ の値を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ 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\ \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 $ - 入力に含まれる値は全て整数である ### Sample Explanation 1 上から $ i $ 行目、左から $ j $ 列目に $ \max(a_i,\ b_j) $ を書き込んだマス目は、$ 4 $ 回のクエリで以下のように変化します。 !\[\](https://img.atcoder.jp/ghi/9a4098e2aa50b21c51ce3664d278ba87.png) ### Sample Explanation 3 出力する整数は $ 32 $ bit 整数型に収まらない可能性があります。