概要

カードの追加・除去・確認操作をシミュレートし、各確認操作で得られたXOR値について、直近の同じ値を持つ確認操作の番号を求める問題です。

考察

素朴なアプローチとして、各操作ごとにカードの山全体のXORを計算しようとすると、確認操作のたびに全カードを走査する必要があり、最悪ケースで \(O(N^2)\) の時間がかかり、制約 \(N \leq 2 \times 10^5\) ではTLEになります。

重要な観察は、カードの操作がスタック構造（LIFO）であることです。追加操作（PUT）ではカードを積み、除去操作（REMOVE）では一番上のカードを取り除きます。この性質から、現在のXOR値は直前のXOR値と新たなカードの値のXORで簡単に計算できます（追加時：current_xor ^ c、除去時：current_xor ^ removed_card）。

また、各確認操作で得られたXOR値を記録し、直近の出現位置を辞書で管理することで、効率的に過去の同じ値を持つ確認操作を検索できます。

アルゴリズム

1. 現在のXOR値 current_xor を0で初期化
2. 各操作を順に処理：
   • PUT c：current_xor に c のXORを適用
   • REMOVE：取り除くカードの値（スタックのtop）で current_xor のXORを適用
   • LOOK：現在の current_xor を記録し、辞書で直近の出現位置を検索。見つかればその番号を、なければ-1を結果に追加。辞書の該当値を現在の確認操作番号で更新
3. 全ての確認操作の結果を出力

スタック自体はカードの値を保持するために使用しますが、XOR値の計算にはスタック全体を走査せず、差分更新します。

計算量

• 時間計算量: \(O(N)\)
  • 各操作は定数時間で処理可能（辞書操作は平均 \(O(1)\)）
• 空間計算量: \(O(N)\)
  • スタックと辞書のサイズは最大 \(N\) に比例

実装のポイント

• XORの性質を利用：同じ値を2回XORすると0になる（除去操作で値を打ち消せる）

• 辞書 xor_to_last_index で各XOR値の直近の出現位置を管理

• 確認操作の番号を look_count でカウント

• 結果はタプルで保持し、最後にまとめて出力

  ソースコード

import sys

def main():
    data = sys.stdin.read().splitlines()
    n = int(data[0])
    events = data[1:1+n]
    
    stack = []
    xor_stack = []
    current_xor = 0
    results = []
    xor_to_last_index = {}
    
    look_count = 0
    
    for event in events:
        parts = event.split()
        if parts[0] == 'PUT':
            c = int(parts[1])
            stack.append(c)
            current_xor ^= c
            xor_stack.append(current_xor)
        elif parts[0] == 'REMOVE':
            removed = stack.pop()
            current_xor ^= removed
            xor_stack.append(current_xor)
        elif parts[0] == 'LOOK':
            look_count += 1
            v = current_xor
            if v in xor_to_last_index:
                results.append((look_count, xor_to_last_index[v]))
            else:
                results.append((look_count, -1))
            xor_to_last_index[v] = look_count
    
    for idx, val in results:
        print(val)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。