B - Warehouse Inventory Management Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は物流センターで倉庫の管理を担当しています。

物流センターには N 個の倉庫があり、各倉庫には 1 から N までの番号が付けられています。はじめ、倉庫 i (1 \leq i \leq N) には重さ V_i の荷物が 1 つだけ保管されています。

青木君は配送担当で、Q 個の指示を順番に高橋君に伝えます。各指示は次の 2 種類のいずれかです。

  • 種類 1：「倉庫 a にある荷物をすべて、倉庫 b に移動する」（a \neq b）。倉庫 a に現在ある荷物をすべて倉庫 b に移動させます。移動後、倉庫 a は空になります。倉庫 b にはもともと保管されていた荷物と、倉庫 a から移動してきた荷物の両方が保管されます。倉庫 a が空の場合、何も起こりません。
  • 種類 2：「倉庫 c にある荷物の重さの合計を報告する」。倉庫 c に現在保管されているすべての荷物の重さの合計を出力します。倉庫 c が空の場合は 0 を出力します。

高橋君は指示を 1 番目から順に処理していきます。種類 2 の指示それぞれについて、出力すべき値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 各指示は種類 1 または種類 2 のいずれかである
  • 種類 1 の指示において、1 \leq a \leq N, 1 \leq b \leq N, a \neq b
  • 種類 2 の指示において、1 \leq c \leq N
  • 入力はすべて整数である

入力

N Q
V_1 V_2 \ldots V_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
  • 1 行目には、倉庫の数を表す整数 N と指示の数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、初期状態で倉庫 i に保管されている荷物の重さを表す整数 V_1, V_2, \ldots, V_N が、スペース区切りで与えられる。
  • 続く Q 行にわたって、指示の情報が 1 つずつ与えられる。各指示 \text{query}_i は以下のいずれかの形式である。
  • 種類 1 の場合：1 a b（倉庫 a の荷物をすべて倉庫 b に移動する）
  • 種類 2 の場合：2 c（倉庫 c の荷物の重さの合計を求める）

出力

種類 2 の指示それぞれについて、指示が与えられた順に、出力すべき値を 1 行ずつ出力せよ。種類 2 の指示が存在しない場合は何も出力しない。

入力例 1

3 5
10 20 30
1 1 2
2 2
2 1
1 3 2
2 2

出力例 1

30
0
60

入力例 2

4 6
5 15 25 35
2 4
1 1 3
1 2 3
2 3
1 1 4
2 1

出力例 2

35
45
0

入力例 3

8 12
100 200 300 400 500 600 700 800
1 1 2
1 3 2
2 2
1 4 5
1 6 5
2 5
1 2 5
2 5
1 7 8
1 8 5
2 5
2 7

出力例 3

600
1500
2100
3600
0

入力例 4

10 15
1000000000 999999999 888888888 777777777 666666666 555555555 444444444 333333333 222222222 111111111
1 1 2
1 3 2
1 4 2
2 2
1 5 6
1 7 6
1 8 6
2 6
1 2 10
1 6 10
2 10
1 9 10
2 10
2 1
2 5

出力例 4

3666666664
1999999998
5777777773
5999999995
0
0

入力例 5

1 1
1000000000
2 1

出力例 5

1000000000

Score : 266 pts

Problem Statement

Takahashi is in charge of warehouse management at a logistics center.

The logistics center has N warehouses, each numbered from 1 to N. Initially, warehouse i (1 \leq i \leq N) stores exactly one item with weight V_i.

Aoki is in charge of delivery and gives Q instructions to Takahashi in order. Each instruction is one of the following two types:

  • Type 1: "Move all items in warehouse a to warehouse b" (a \neq b). All items currently in warehouse a are moved to warehouse b. After the move, warehouse a becomes empty. Warehouse b will then store both the items it originally had and the items moved from warehouse a. If warehouse a is empty, nothing happens.
  • Type 2: "Report the total weight of items in warehouse c". Output the total weight of all items currently stored in warehouse c. If warehouse c is empty, output 0.

Takahashi processes the instructions in order starting from the first. For each Type 2 instruction, determine the value that should be output.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • Each instruction is either Type 1 or Type 2
  • For Type 1 instructions, 1 \leq a \leq N, 1 \leq b \leq N, a \neq b
  • For Type 2 instructions, 1 \leq c \leq N
  • All input values are integers

Input

N Q
V_1 V_2 \ldots V_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
  • The first line contains two space-separated integers: N, the number of warehouses, and Q, the number of instructions.
  • The second line contains N space-separated integers V_1, V_2, \ldots, V_N, where V_i represents the weight of the item initially stored in warehouse i.
  • The following Q lines each contain one instruction. Each instruction \text{query}_i is in one of the following formats:
  • Type 1: 1 a b (move all items from warehouse a to warehouse b)
  • Type 2: 2 c (find the total weight of items in warehouse c)

Output

For each Type 2 instruction, output the corresponding value on a separate line, in the order the instructions were given. If there are no Type 2 instructions, output nothing.

Sample Input 1

3 5
10 20 30
1 1 2
2 2
2 1
1 3 2
2 2

Sample Output 1

30
0
60

Sample Input 2

4 6
5 15 25 35
2 4
1 1 3
1 2 3
2 3
1 1 4
2 1

Sample Output 2

35
45
0

Sample Input 3

8 12
100 200 300 400 500 600 700 800
1 1 2
1 3 2
2 2
1 4 5
1 6 5
2 5
1 2 5
2 5
1 7 8
1 8 5
2 5
2 7

Sample Output 3

600
1500
2100
3600
0

Sample Input 4

10 15
1000000000 999999999 888888888 777777777 666666666 555555555 444444444 333333333 222222222 111111111
1 1 2
1 3 2
1 4 2
2 2
1 5 6
1 7 6
1 8 6
2 6
1 2 10
1 6 10
2 10
1 9 10
2 10
2 1
2 5

Sample Output 4

3666666664
1999999998
5777777773
5999999995
0
0

Sample Input 5

1 1
1000000000
2 1

Sample Output 5

1000000000