Overview

This is a simulation problem where we process movement of packages between warehouses (type 1) and queries for the total weight of packages in a specified warehouse (type 2). By managing only the total weight of each warehouse, there is no need to track individual packages.

Analysis

Key Insight: No Need to Manage Individual Packages

At first glance, it might seem necessary to manage which packages are in each warehouse using lists or similar data structures. However, reading the problem carefully, type 2 instructions only ask for the total weight.

For example, if warehouse 1 has packages of weight 3 and 5, and warehouse 2 has a package of weight 7, and the instruction is “move all packages from warehouse 1 to warehouse 2”:

• Warehouse 1 total: \(3 + 5 = 8\) → after moving: \(0\)
• Warehouse 2 total: \(7\) → after moving: \(7 + 8 = 15\)

In this way, the move operation can be expressed using only addition of totals and resetting to 0.

Comparison with the Naive Approach

If we manage the packages in each warehouse using lists and move elements one by one for each transfer, the worst case requires \(O(N)\) operations per move, resulting in \(O(NQ)\) overall, which risks TLE.

By managing only the total values, each operation can be processed in \(O(1)\).

Algorithm

1. Prepare an array warehouse of size \(N+1\), where warehouse[i] stores the total weight of packages in warehouse \(i\) (1-indexed).
2. Initialize with warehouse[i] = V[i].
3. Process the \(Q\) instructions in order:
   • Type 1 (1 a b): Set warehouse[b] += warehouse[a], then set warehouse[a] = 0.
   • Type 2 (2 c): Output the value of warehouse[c].

Concrete Example

When \(N = 3\), \(V = [10, 20, 30]\):

Operation	warehouse[1]	warehouse[2]	warehouse[3]	Output
Initial state	10	20	30	-
1 1 3 (warehouse 1 → warehouse 3)	0	20	40	-
2 3 (report warehouse 3)	0	20	40	40
1 2 3 (warehouse 2 → warehouse 3)	0	0	60	-
2 1 (report warehouse 1)	0	0	60	0

Complexity

• Time complexity: \(O(N + Q)\) — \(O(N)\) for initialization, \(O(1)\) for processing each query
• Space complexity: \(O(N)\) — array to hold the total value for each warehouse

Implementation Notes

• Since warehouse numbers range from \(1\) to \(N\), allocating the array with size \(N+1\) and using 1-indexed access prevents off-by-one errors.

• Even when warehouse \(a\) is empty (total value is 0) in type 1, it simply results in warehouse[b] += 0, so no special branching is needed.

• In Python, input processing can become a bottleneck, so for large inputs it’s worth considering the use of sys.stdin. However, under the constraints of this problem (\(N, Q \leq 2 \times 10^5\)), the standard input() is sufficient.

  Source Code

N, Q = map(int, input().split())
V = list(map(int, input().split()))
warehouse = [0] * (N + 1)
for i in range(N):
    warehouse[i + 1] = V[i]
for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        a, b = query[1], query[2]
        warehouse[b] += warehouse[a]
        warehouse[a] = 0
    else:
        c = query[1]
        print(warehouse[c])

---

This editorial was generated by claude4.6opus-thinking.