← 返回题目列表

AtCoder · awc0029_b

B. 仓库库存管理

中文机器翻译题面 查看原题

分数: 266 分

问题陈述

高桥负责物流中心的仓库管理。

物流中心有 N 仓库,每个编号从 1 to N。最初,仓库 i (1 \leq i \leq N) 只存储一件有重量的物品 V_i.

青木负责送货并给予 Q 按顺序向高桥发出指示。每条指令都是以下两种类型之一:

  • 类型 1: "移动仓库中的所有物品 a 到仓库 b" (a \neq b)。当前仓库中的所有物品 a 已移至仓库 b。搬家后,仓库 a 变为空。仓库 b 将存储原来拥有的物品和从仓库移出的物品 a。如果仓库 a 为空,没有任何反应。
  • 类型 2: "报告仓库中物品的总重量 c".输出当前仓库中存储的所有物品的总重量 c。如果仓库 c 为空,输出 0.

Takahashi 从第一个指令开始按顺序处理指令。对于每个类型 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
  • 第一行包含两个空格分隔的整数: N,仓库数量,以及 Q,指令数。
  • 第二行包含 N 空格分隔的整数 V_1, V_2, \ldots, V_N,其中 V_i 表示最初存放在仓库中的物品的重量 i.
  • 以下 Q 行每行包含一条指令。每条指令 \text{query}_i 采用以下格式之一:
  • 类型 1: 1 a b (从仓库中移出所有物品 a 到仓库 b)
  • 类型 2: 2 c (查找仓库中物品的总重量 c)

输出

对于每个类型 2 指令,按照给出指令的顺序在单独的行上输出相应的值。如果没有类型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