概要

この問題は、スタック（山）の状態に応じて変化する「全要素のビットごとの XOR（排他的論理和）」を管理し、各確認操作において過去に同じ XOR 値が現れた直近のタイミングを特定する問題です。

考察

1. XOR の性質を利用する

「現在の山にあるすべてのカードの XOR 和」を毎回最初から計算すると、山にあるカードの枚数を \(M\) としたとき、1回の LOOK 操作に \(O(M)\) かかってしまいます。最悪の場合 \(M\) は \(N\) に比例するため、全体の計算量が \(O(N^2)\) となり、実行時間制限に間に合いません。

しかし、XOR には 「同じ値を2回 XOR すると元に戻る（\(A \oplus B \oplus B = A\)）」 という重要な性質があります。これを利用すると、現在の XOR 和を以下のように効率的に更新できます。 - PUT c: 現在の XOR 和に \(c\) を XOR する。 - REMOVE: 山の一番上の値を \(v\) とすると、現在の XOR 和に \(v\) を XOR する（これにより \(v\) の影響が打ち消される）。

これにより、各操作を \(O(1)\) で処理できるようになります。

2. 直近の同じ値を高速に見つける

各 LOOK 操作で得られた XOR 値について、「過去に同じ値がいつ現れたか」を記録しておく必要があります。これには 連想配列（Python の辞書） を使うのが最適です。 - キー：これまでに現れた XOR 値 - 値：その XOR 値が最後に現れた LOOK 操作の番号

LOOK 操作が行われるたびに、辞書から現在の XOR 値に対応する番号を取得し、その後で辞書の値を現在の操作番号に更新すれば、常に「直近の番号」を取得できます。

アルゴリズム

1. データの準備:
   • カードの値を管理するスタック（リスト）
   • 現在の XOR 総和を保持する変数 current_xor（初期値 0）
   • XOR 値と LOOK 番号を紐付ける辞書 last_seen
   • LOOK 操作の回数を数える変数 look_count
2. 各操作の処理:
   • PUT c: スタックに \(c\) を追加し、current_xor ^= c を行う。
   • REMOVE: スタックから値を pop し、その値を current_xor に XOR する。
   • LOOK:
     1. look_count をインクリメントする。
     2. last_seen に current_xor が存在すればその値を記録し、なければ -1 を記録する。
     3. last_seen[current_xor] を現在の look_count で更新する。
3. 結果の出力: 記録した結果を順に出力する。

計算量

• 時間計算量: \(O(N)\)
  • 各操作（PUT, REMOVE, LOOK）は、スタックの操作や辞書の読み書きを含めてすべて平均 \(O(1)\) で処理されます。操作回数は \(N\) なので、全体で \(O(N)\) となります。
• 空間計算量: \(O(N)\)
  • スタック、辞書、および結果を格納するリストのサイズは最大で \(N\) に比例します。

実装のポイント

• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と大きいため、Python では input() ではなく sys.stdin.read().split() を使って一括で入力を読み込み、sys.stdout.write() で一括出力することで実行時間を大幅に短縮できます。

• 初期値: XOR の単位元は \(0\) なので、current_xor の初期値は \(0\) とします。ただし、問題文の条件より LOOK 時には必ずカードが1枚以上あるため、空の状態の XOR 値が参照されることはありません。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを一度に読み込み、空白で分割してリストにする
    # これにより、大量の入力に対しても高速に処理が可能
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 操作の総回数 N
    n = int(input_data[0])
    
    # カードの山を管理するスタック
    stack = []
    # 現在の山にあるすべてのカードの XOR 和
    current_xor = 0
    # 各 XOR 値が最後にどの確認操作（LOOK）で現れたかを記録する辞書
    # キー: XOR 値, 値: 確認操作の番号（1-indexed）
    last_seen = {}
    # 確認操作の回数をカウント
    look_count = 0
    
    # 各確認操作の結果を格納するリスト
    results = []
    
    # 入力リストを走査するためのインデックス
    idx = 1
    for _ in range(n):
        op = input_data[idx]
        idx += 1
        
        if op == 'PUT':
            # カードを追加する操作
            val = int(input_data[idx])
            idx += 1
            stack.append(val)
            # XOR の性質: A ^ B ^ B = A なので、追加時はそのまま XOR をとる
            current_xor ^= val
            
        elif op == 'REMOVE':
            # カードを取り除く操作（山に1枚以上あることが保証されている）
            top = stack.pop()
            # 取り除くカードの値を XOR することで、その値の影響を消す
            current_xor ^= top
            
        elif op == 'LOOK':
            # 現在の XOR 和を確認する操作（山に1枚以上あることが保証されている）
            look_count += 1
            # 同じ XOR 値が過去に現れたか辞書で確認
            # 存在すればその番号を、なければ -1 を取得
            prev_look_idx = last_seen.get(current_xor, -1)
            results.append(prev_look_idx)
            # 現在の確認操作の番号で辞書を更新
            last_seen[current_xor] = look_count
            
    # すべての確認操作の結果を改行区切りで一括出力
    if results:
        sys.stdout.write('\n'.join(map(str, results)) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。