概要

カードの山に対する PUT / REMOVE / LOOK を順に処理し、各 LOOK で得られる「山全体の XOR 値」が過去いつ（何回目の LOOK）に最後に出たかを答える問題です。

考察

重要な気づき 1：山全体の XOR は「差分更新」できる

山にあるカードの XOR を毎回 1 枚ずつ計算し直すと、LOOK のたびに最大で山の枚数ぶんかかります。最悪ケースでは - PUT を \(10^5\) 回して山を大きくし、 - LOOK を \(10^5\) 回する といった入力があり得て、素朴に毎回 XOR を取り直すと合計 \(O(N^2)\) となり TLE になります。

ここで XOR の性質を使います：

• XOR は可換・結合的なので順序を気にしなくてよい
• \(a \oplus a = 0\)
• \(x \oplus a \oplus a = x\)（同じ値を 2 回 XOR すると元に戻る）

よって、山全体の XOR 値を xor_all として持っておけば、 - PUT c：xor_all ^= c - REMOVE（取り除いた値を \(x\) とする）：xor_all ^= x で常に最新の山全体 XOR を \(O(1)\) で更新できます。

重要な気づき 2：「同じ XOR が最後に出た LOOK 回数」を辞書で持つ

求めたいのは、各 LOOK の値 \(v_i\) について「直近で同じ値が出た LOOK の番号」なので、 - last[v] = 最後に XOR 値 v が出た LOOK の番号 を辞書（連想配列）で管理すればよいです。

例えば LOOK の結果が順に 5, 7, 5 なら、 - 1 回目（5）：過去にないので -1、last[5]=1 - 2 回目（7）：過去にないので -1、last[7]=2 - 3 回目（5）：last[5]=1 があるので 1 を出し、last[5]=3 に更新 となります。

アルゴリズム

1. スタック stack を用意し、山のカードを管理する（REMOVE で取り出す値が必要）。
2. 変数 xor_all に「現在の山全体の XOR」を保持する（初期値 0）。
3. 辞書 last に「XOR 値 → 最後にその値が出た LOOK の番号」を保持する。
4. LOOK の回数カウンタ look_idx を 1 から数える。
5. 各操作を順に処理：
   • PUT c：
     • stack.append(c)
     • xor_all ^= c
   • REMOVE：
     • x = stack.pop()
     • xor_all ^= x
   • LOOK：
     • look_idx += 1
     • v = xor_all
     • 答えは last にあればその番号、なければ -1
     • その後 last[v] = look_idx に更新

これで各操作をすべて \(O(1)\) で処理できます。

計算量

• 時間計算量: \(O(N)\)（各操作が定数時間）
• 空間計算量: \(O(N)\)（スタックと辞書に最大 \(N\) 要素）

実装のポイント

• REMOVE では「取り除いたカードの値」を使って xor_all を更新する必要があるため、カードは必ずスタックに積んでおきます。

• LOOK の番号付けは「LOOK が出た回数」なので、全操作番号とは別に look_idx を持ちます。

• last.get(v, -1) を使うと「なければ -1」を簡潔に書けます。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    stack = []
    xor_all = 0
    last = {}  # xor value -> last LOOK index
    ans = []
    look_idx = 0

    for _ in range(N):
        parts = input().split()
        if parts[0] == b'PUT':
            c = int(parts[1])
            stack.append(c)
            xor_all ^= c
        elif parts[0] == b'REMOVE':
            x = stack.pop()
            xor_all ^= x
        else:  # LOOK
            look_idx += 1
            v = xor_all
            ans.append(str(last.get(v, -1)))
            last[v] = look_idx

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

if __name__ == "__main__":
    main()

---

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