D - 高橋君の価格調整 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は N 個の商品を販売するオンラインショップを運営しています。

最初、各商品 i (1 \leq i \leq N) の価格は A_i 円に設定されています。高橋君は販売開始前に、決められたルールに従って Q 回の「価格調整」を 1 番目から Q 番目まで順番に行います。

j 番目 (1 \leq j \leq Q) の価格調整では、種類 T_j、変更後の価格 X_j、取り消しフラグ R_j が与えられ、以下の手順 1〜3 をこの順に実行します。

  1. 対象商品の選択：直前の価格調整が完了した時点（j = 1 のときは初期状態）での各商品の価格に基づき、対象となる商品を 1 つ選ぶ。
  • T_j = 1 の場合：価格が最も高い商品を選ぶ。価格が最も高い商品が複数あるときは、その中で商品番号が最も小さいものを選ぶ。
  • T_j = 2 の場合：価格が最も低い商品を選ぶ。価格が最も低い商品が複数あるときは、その中で商品番号が最も小さいものを選ぶ。
  1. 価格の変更：手順 1 で選んだ商品の価格を X_j 円に変更する。
  1. 取り消しの判定：取り消しフラグ R_j の値を確認する。
  • R_j = 0 の場合：手順 2 の変更をそのまま確定する。
  • R_j = 1 の場合：手順 2 で行った価格変更を取り消し、選んだ商品の価格を手順 2 の実行前の値に戻す。

ここで、j 番目の価格調整の「完了」とは、手順 1〜3 をすべて実行し終えた状態を指します。R_j = 1 の場合は手順 3 で価格が元に戻されるため、結果として j 番目の価格調整の前後で各商品の価格は変化しません。ただし、R_j = 1 の場合でも手順 1 の対象商品の選択は行われることに注意してください。

すべての価格調整が終わった後の、全商品の価格の合計を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • T_j \in \{1, 2\} (1 \leq j \leq Q)
  • 1 \leq X_j \leq 10^9 (1 \leq j \leq Q)
  • R_j \in \{0, 1\} (1 \leq j \leq Q)
  • 入力はすべて整数である。

入力

N Q
A_1 A_2 \ldots A_N
T_1 X_1 R_1
T_2 X_2 R_2
\vdots
T_Q X_Q R_Q
  • 1 行目には、商品の数 N と価格調整の回数 Q がスペース区切りで与えられる。
  • 2 行目には、各商品の初期価格 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
  • 3 行目から Q 行にわたって、各価格調整の情報が与えられる。
  • 2 + j 行目には、j 番目の調整の種類 T_j（1：最も高い商品を選ぶ、2：最も低い商品を選ぶ）、変更後の価格 X_j、取り消しフラグ R_j（0：変更を確定、1：変更を取り消し）がスペース区切りで与えられる。

出力

すべての価格調整が終わった後の、全商品の価格の合計を 1 行で出力せよ。

入力例 1

3 4
10 20 20
1 5 0
2 30 1
2 15 0
1 8 0

出力例 1

33

入力例 2

4 5
5 5 5 5
2 1 0
1 10 1
1 7 0
2 9 0
2 3 1

出力例 2

26

入力例 3

8 12
100 50 100 75 25 75 50 25
1 60 0
1 40 1
2 90 0
2 10 0
1 30 0
2 80 1
1 110 0
2 55 0
1 65 1
2 20 0
1 45 0
2 70 0

出力例 3

480

入力例 4

15 25
1000 500 1500 500 2000 750 1250 1000 250 1750 250 1500 750 2000 1250
1 300 0
2 1800 0
1 600 1
2 400 0
1 2200 0
1 100 0
2 900 1
2 50 0
1 1600 0
2 1400 0
1 700 1
2 2100 0
1 800 0
2 1200 0
1 500 0
2 1900 1
1 1300 0
2 1100 0
1 200 0
2 1700 0
1 1000 1
2 300 0
1 2400 0
2 600 1
1 150 0

出力例 4

14250

入力例 5

1 1
1000000000
1 1 1

出力例 5

1000000000

Score : 400 pts

Problem Statement

Takahashi runs an online shop that sells N products.

Initially, the price of each product i (1 \leq i \leq N) is set to A_i yen. Before starting sales, Takahashi performs Q "price adjustments" in order from the 1-st to the Q-th, following predetermined rules.

For the j-th (1 \leq j \leq Q) price adjustment, a type T_j, a new price X_j, and a cancellation flag R_j are given, and the following steps 1–3 are executed in this order.

  1. Selection of target product: Based on the prices of all products at the time the previous price adjustment was completed (or the initial state when j = 1), select one target product.
  • If T_j = 1: Select the product with the highest price. If there are multiple products with the highest price, select the one with the smallest product number among them.
  • If T_j = 2: Select the product with the lowest price. If there are multiple products with the lowest price, select the one with the smallest product number among them.
  1. Price change: Change the price of the product selected in step 1 to X_j yen.
  1. Cancellation check: Check the value of the cancellation flag R_j.
  • If R_j = 0: The change made in step 2 is finalized as is.
  • If R_j = 1: The price change made in step 2 is cancelled, and the price of the selected product is reverted to the value it had before step 2 was executed.

Here, the "completion" of the j-th price adjustment refers to the state after all of steps 1–3 have been executed. If R_j = 1, the price is reverted in step 3, so as a result, the prices of all products do not change before and after the j-th price adjustment. However, note that even when R_j = 1, the selection of the target product in step 1 is still performed.

Find the total price of all products after all price adjustments have been completed.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • T_j \in \{1, 2\} (1 \leq j \leq Q)
  • 1 \leq X_j \leq 10^9 (1 \leq j \leq Q)
  • R_j \in \{0, 1\} (1 \leq j \leq Q)
  • All input values are integers.

Input

N Q
A_1 A_2 \ldots A_N
T_1 X_1 R_1
T_2 X_2 R_2
\vdots
T_Q X_Q R_Q
  • The first line contains the number of products N and the number of price adjustments Q, separated by a space.
  • The second line contains the initial prices A_1, A_2, \ldots, A_N of each product, separated by spaces.
  • The following Q lines contain the information for each price adjustment.
  • The (2 + j)-th line contains the type T_j of the j-th adjustment (1: select the most expensive product, 2: select the cheapest product), the new price X_j, and the cancellation flag R_j (0: finalize the change, 1: cancel the change), separated by spaces.

Output

Output in one line the total price of all products after all price adjustments have been completed.

Sample Input 1

3 4
10 20 20
1 5 0
2 30 1
2 15 0
1 8 0

Sample Output 1

33

Sample Input 2

4 5
5 5 5 5
2 1 0
1 10 1
1 7 0
2 9 0
2 3 1

Sample Output 2

26

Sample Input 3

8 12
100 50 100 75 25 75 50 25
1 60 0
1 40 1
2 90 0
2 10 0
1 30 0
2 80 1
1 110 0
2 55 0
1 65 1
2 20 0
1 45 0
2 70 0

Sample Output 3

480

Sample Input 4

15 25
1000 500 1500 500 2000 750 1250 1000 250 1750 250 1500 750 2000 1250
1 300 0
2 1800 0
1 600 1
2 400 0
1 2200 0
1 100 0
2 900 1
2 50 0
1 1600 0
2 1400 0
1 700 1
2 2100 0
1 800 0
2 1200 0
1 500 0
2 1900 1
1 1300 0
2 1100 0
1 200 0
2 1700 0
1 1000 1
2 300 0
1 2400 0
2 600 1
1 150 0

Sample Output 4

14250

Sample Input 5

1 1
1000000000
1 1 1

Sample Output 5

1000000000