分数: 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