Overview

This is a problem where you only need to manage the “total weight” of packages in each warehouse, and for move instructions, you transfer the total values to answer all queries efficiently.

Analysis

What this problem requires is only the total weight of packages in each warehouse. We are never asked where individual packages came from or how many there are.

• Type 1 (move all packages from warehouse \(a\) to warehouse \(b\)):
  All we need to do is “add the total weight of \(a\) to \(b\), and set \(a\) to \(0\).”
• Type 2 (report the total weight of warehouse \(c\)):
  Simply output the current total weight.

Why a naive approach is dangerous

For example, if each warehouse holds a “list (array) of packages” and we concatenate lists on every move: - In the worst case, the same packages are copied and moved repeatedly, potentially blowing up to \(O(NQ)\) total operations. - Since \(N, Q \le 2 \times 10^5\), this will certainly result in a time limit exceeded.

Key insight

Since “only the total weight is needed,” it is sufficient to maintain just a single number (total weight) for each warehouse.
Move operations are completed with just addition and assignment of total values.

(Example)
If warehouse 1 has a total of 10 and warehouse 2 has a total of 7, then executing 1 1 2 (move from 1 → 2) results in
warehouse 2’s total becoming \(7 + 10 = 17\), and warehouse 1 becomes \(0\).

Algorithm

Let array s[i] be “the total weight of packages in warehouse \(i\).”

Initialization: - s[i] = V_i

Query processing: - Type 1 1 a b
- s[b] += s[a]
- s[a] = 0 - Type 2 2 c
- Output s[c]

With this, each query can be processed in constant time.

Complexity

• Time complexity: \(O(N + Q)\) (initialization \(O(N)\), each query \(O(1)\))
• Space complexity: \(O(N)\) (total weight array s)

Implementation Notes

• The total weight can become very large (up to around \(N \times 10^9\)).
  Python’s int supports arbitrary precision, so it is safe as-is.

• Since the input can be up to around \(4 \times 10^5\) lines, we read everything at once using sys.stdin.buffer.read() and split() for speedup.

• When s[a] == 0 in Type 1, nothing changes, so in the code we use if s[a]: to avoid unnecessary operations (this isn’t required for correctness, but it speeds things up).

  Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    Q = next(it)

    s = [0] * (N + 1)
    for i in range(1, N + 1):
        s[i] = next(it)

    out = []
    for _ in range(Q):
        t = next(it)
        if t == 1:
            a = next(it)
            b = next(it)
            if s[a]:
                s[b] += s[a]
                s[a] = 0
        else:
            c = next(it)
            out.append(str(s[c]))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.