概要

倉庫間の荷物の移動（種類1）と、指定倉庫の荷物の重さの合計の問い合わせ（種類2）を処理するシミュレーション問題です。各倉庫の重さの合計値だけを管理すれば、個々の荷物を追跡する必要はありません。

考察

重要な気づき：個々の荷物を管理する必要はない

一見すると、各倉庫にどの荷物が入っているかをリストなどで管理する必要がありそうに思えます。しかし、問題をよく読むと、種類2の指示で求められるのは 重さの合計 だけです。

例えば、倉庫1に重さ 3, 5 の荷物があり、倉庫2に重さ 7 の荷物がある状態で「倉庫1の荷物をすべて倉庫2に移動する」と指示された場合：

• 倉庫1の合計：\(3 + 5 = 8\) → 移動後 \(0\)
• 倉庫2の合計：\(7\) → 移動後 \(7 + 8 = 15\)

このように、合計値の足し算と0への初期化だけで移動操作を表現できます。

素朴なアプローチとの比較

もし各倉庫にある荷物をリストで管理し、移動のたびにリストの要素を1つずつ移す実装をすると、最悪の場合1回の移動で \(O(N)\) の操作が必要になり、全体で \(O(NQ)\) となってTLEの危険があります。

合計値だけを管理すれば、各操作が \(O(1)\) で処理できます。

アルゴリズム

1. サイズ \(N+1\) の配列 warehouse を用意し、warehouse[i] に倉庫 \(i\) の荷物の重さの合計を格納する（1-indexed）。
2. 初期値として warehouse[i] = V[i] を設定する。
3. \(Q\) 個の指示を順に処理する：
   • 種類1（1 a b）：warehouse[b] += warehouse[a] とした後、warehouse[a] = 0 にする。
   • 種類2（2 c）：warehouse[c] の値を出力する。

具体例

\(N = 3\), \(V = [10, 20, 30]\) のとき：

操作	warehouse[1]	warehouse[2]	warehouse[3]	出力
初期状態	10	20	30	-
1 1 3（倉庫1→倉庫3）	0	20	40	-
2 3（倉庫3を報告）	0	20	40	40
1 2 3（倉庫2→倉庫3）	0	0	60	-
2 1（倉庫1を報告）	0	0	60	0

計算量

• 時間計算量: \(O(N + Q)\) — 初期化に \(O(N)\)、各クエリの処理に \(O(1)\)
• 空間計算量: \(O(N)\) — 倉庫ごとの合計値を保持する配列

実装のポイント

• 倉庫番号が \(1\) から \(N\) なので、配列を \(N+1\) の大きさで確保し 1-indexed で扱うとインデックスのずれを防げます。

• 種類1で倉庫 \(a\) が空（合計値が0）の場合も、warehouse[b] += 0 となるだけなので特別な分岐は不要です。

• Python では入力処理がボトルネックになることがあるため、大量の入力がある場合は sys.stdin の利用を検討するとよいですが、本問題の制約（\(N, Q \leq 2 \times 10^5\)）では標準の input() でも十分間に合います。

  ソースコード

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

---

この解説は claude4.6opus-thinking によって生成されました。