概要

各倉庫にある荷物の「重さの合計」だけを管理し、移動指示では合計値を移し替えることで、全ての問い合わせに高速に答える問題です。

考察

この問題で求められるのは、各倉庫に存在する荷物の 総重量 だけです。個々の荷物がどこから来たか・何個あるかは一切問われません。

• 種類 1（倉庫 \(a\) の荷物をすべて \(b\) へ移動）
  必要なのは「\(a\) の総重量を \(b\) に足し、\(a\) を \(0\) にする」ことだけです。
• 種類 2（倉庫 \(c\) の総重量を報告）
  その時点の総重量を出力するだけです。

素朴な方法が危険な理由

例えば各倉庫に「荷物のリスト（配列）」を持ち、移動のたびにリストを結合すると、 - 最悪の場合、同じ荷物が何度もコピー・移動されてしまい、合計で \(O(NQ)\) のように膨れ上がる可能性があります。 - \(N,Q \le 2 \times 10^5\) なので、これは確実に時間切れになります。

重要な気づき

「総重量しか必要ない」ので、各倉庫について 1つの数値（総重量） だけ持てば十分です。
移動操作も合計値の加算と代入だけで終わります。

（例）
倉庫 1 に合計 10、倉庫 2 に合計 7 があるとき、1 1 2（1→2へ移動）をすると
倉庫 2 の合計は \(7+10=17\)、倉庫 1 は \(0\) になります。

アルゴリズム

配列 s[i] を「倉庫 \(i\) にある荷物の総重量」とする。

初期化： - s[i] = V_i

クエリ処理： - 種類 1 1 a b
- s[b] += s[a]
- s[a] = 0 - 種類 2 2 c
- s[c] を出力

これで、各クエリを定数時間で処理できます。

計算量

• 時間計算量: \(O(N + Q)\)（初期化 \(O(N)\)、各クエリ \(O(1)\)）
• 空間計算量: \(O(N)\)（総重量配列 s）

実装のポイント

• 重さの合計は大きくなり得ます（最大で \(N \times 10^9\) 程度）
  Python の int は多倍長なのでそのままで安全です。

• 入力が最大 \(4 \times 10^5\) 行規模になり得るため、sys.stdin.buffer.read() でまとめて読み、split() して高速化しています。

• 種類 1 で s[a] == 0 のときは何も起きないため、コードでは if s[a]: として無駄な処理を避けています（なくても正しいですが高速化になります）。

  ソースコード

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()

---

この解説は gpt-5.2-high によって生成されました。