AT_pakencamp_2019_day3_g プレゼント配り2

[problemUrl]: https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_g E869120 君は「AtCoder サンタ事務局」の社員であり，サンタにプレゼントを効率的に配らせるための仕事を，毎年行っています． さて，今年もクリスマスがやってきました．彼の今年の仕事は，「AtCoder 通り」において，サンタと家の位置の情報を仕入れ，サンタのプレゼント配りを効率化することです． AtCoder 通りは，西から東に走る，長さ $ 1\ 000\ 000\ 000 $ の道路です．最初，E869120 君に入ってきた，家の位置とサンタの位置の情報は，以下のようになります． - その通りに家は $ N $ 軒ある．家には $ 1,\ 2,\ ...,\ N $ と番号づけられており，番号 $ i $ の家は，道路の西端から $ A_i $ メートルの位置にある． - その通りにサンタは $ M $ 人いる．サンタには $ 1,\ 2,\ ...,\ M $ と番号づけられており，番号 $ i $ のサンタは，道路の西端から $ B_i $ メートルの位置にいる． しかし，AtCoder 通りでは，家の引っ越しやサンタの移動などがたびたび起こります．そのため，クリスマスまでに $ Q $ 回の情報変更が行われます．$ i $ 回目の情報変更について， - $ T_i\ =\ 1 $ のとき：番号 $ C_i $ の家の位置が，道路の西端から $ D_i $ メートルの位置に変更される． - $ T_i\ =\ 2 $ のとき：番号 $ C_i $ のサンタの位置が，道路の西端から $ D_i $ メートルの位置に変更される． そのとき，$ i\ =\ 0,\ 1,\ 2,\ ...,\ Q $ について，$ i $ 回目の変更直後の情報において，以下の問題に答えてください． - すべての家にプレゼントが配られるために，$ M $ 人のサンタを合計して，何メートル移動する必要があるか，求めよ． - ただし，すべてのサンタは常にプレゼントを十分な個数持っているものとする． - また，サンタは家のある位置に移動することによって，プレゼントを配ることができる．遠い位置からプレゼントを投げて配るなどということはできない．**サンタ達はプレゼントを配り終わった後，元の場所に戻る必要はない．** ただし，「$ 0 $ 回目の変更直後の情報」というのは，最初に E869120 君に入ってきた情報のことを指します．

入力は以下の形式で標準入力から与えられます． > $ N $ $ A_1 $ $ A_2 $ $ A_3 $ ... $ A_N $ $ M $ $ B_1 $ $ B_2 $ $ B_3 $ ... $ B_M $ $ Q $ $ T_1 $ $ C_1 $ $ D_1 $ $ T_2 $ $ C_2 $ $ D_2 $ $ T_3 $ $ C_3 $ $ D_3 $ : : : $ T_Q $ $ C_Q $ $ D_Q $

$ Q+1 $ 行に渡って出力してください． $ i $ 行目には，$ i-1 $ 番目の変更の直後の情報において，サンタの合計移動距離の最小値を出力してください．

### 制約 - $ 1\ \leq\ N\ \leq\ 100\ 000 $ - $ 1\ \leq\ M\ \leq\ 100\ 000 $ - $ 0\ \leq\ Q\ \leq\ 100\ 000 $ - $ 0\ \leq\ A_i\ \leq\ 1\ 000\ 000\ 000 $, $ A_i $ は偶数 - $ 0\ \leq\ B_i\ \leq\ 1\ 000\ 000\ 000 $, $ B_i $ は奇数 - $ 1\ \leq\ T_i\ \leq\ 2 $ - $ T_i\ =\ 1 $ のとき，$ 1\ \leq\ C_i\ \leq\ N $，$ 0\ \leq\ D_i\ \leq\ 1\ 000\ 000\ 000 $ を満たし，$ D_i $ は偶数である． - $ T_i\ =\ 2 $ のとき，$ 1\ \leq\ C_i\ \leq\ M $，$ 0\ \leq\ D_i\ \leq\ 1\ 000\ 000\ 000 $ を満たし，$ D_i $ は奇数である． - $ 2 $ つの家が同じ位置に来るような情報の変更はない． - $ 2 $ つのサンタが同じ位置に来るような情報の変更はない． ### 部分点 この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます． 提出したソースコードの得点は，正解した小課題の点数の合計となります． 1. (2 点) $ M\ =\ 1 $，$ Q\ =\ 0 $． 2. (6 点) $ M\ =\ 2 $，$ Q\ =\ 0 $． 3. (14 点) $ N\ \leq\ 250 $，$ M\ \leq\ 250 $，$ Q\ =\ 0 $． 4. (9 点) $ N\ \leq\ 3\ 000 $，$ M\ \leq\ 3\ 000 $，$ Q\ =\ 0 $． 5. (9 点) $ Q\ =\ 0 $． 6. (35 点) $ N\ \leq\ 40\ 000,\ M\ \leq\ 40\ 000,\ Q\ \leq\ 40\ 000,\ T_i\ =\ 1 $． 7. (19 点) $ N\ \leq\ 40\ 000,\ M\ \leq\ 40\ 000,\ Q\ \leq\ 40\ 000 $． 8. (6 点) 追加の制約はない． ### Sample Explanation 1 以下のようにサンタが移動する場合，合計移動距離 $ 69 $ となり，これが最小です． - サンタ $ 1 $ が家 $ 1 $ に移動し，プレゼントを配る．その時点での移動距離は $ 13 $ である． - サンタ $ 1 $ が家 $ 2 $ に移動し，プレゼントを配る．その時点での移動距離は $ 19 $ である． - サンタ $ 1 $ が家 $ 3 $ に移動し，プレゼントを配る．その時点での移動距離は $ 37 $ である． - サンタ $ 1 $ が家 $ 4 $ に移動し，プレゼントを配る．その時点での移動距離は $ 51 $ である． - サンタ $ 1 $ が家 $ 5 $ に移動し，プレゼントを配る．その時点での移動距離は $ 69 $ である． ### Sample Explanation 2 この入力例は小課題2の制約を満たします． なお，小課題2は，入力例 1 のような $ M\ =\ 1 $ の場合を含まないことにご注意ください． ### Sample Explanation 3 この入力例は小課題 3, 4, 5 の制約を満たします．