概要

スタック（後入れ先出し）構造でカードを管理しながら、確認操作のたびに山全体の XOR 値を求め、同じ XOR 値が得られた直近の過去の確認操作の番号を答える問題です。

考察

重要な気づき：XOR の累積管理

素朴に考えると、LOOK 操作のたびにスタック内の全カードの XOR を計算する必要がありそうですが、それでは毎回 \(O(\text{スタックのサイズ})\) かかり、最悪 \(O(N^2)\) になってしまいます。

しかし、XOR には以下の便利な性質があります：

• 追加時: 新しいカード \(c\) を置いたとき、全体の XOR は xor_val ^ c で更新できる
• 除去時: 一番上のカード \(c\) を取り除いたとき、XOR の性質（\(a \oplus a = 0\)）より、xor_val ^ c で元に戻る

つまり、変数 xor_val を1つ持っておけば、PUT/REMOVE のたびに \(O(1)\) で現在の XOR 値を維持できます。

「同じ XOR 値の直近の LOOK」の高速検索

各 LOOK 操作で得られた XOR 値 \(v_i\) に対して、\(v_j = v_i\) かつ \(j < i\) を満たす 最大の \(j\) を求める必要があります。

これは辞書（ハッシュマップ）を使えば簡単です。XOR 値をキー、その値が最後に現れた LOOK の番号を値として記録しておけば、LOOK のたびに \(O(1)\) で答えが求まります。

具体例で確認しましょう：

操作	xor_val	LOOK番号	辞書の状態	出力
PUT 3	3	-	{}	-
PUT 5	3⊕5=6	-	{}	-
LOOK	6	1	{6:1}	-1
REMOVE	6⊕5=3	-	{6:1}	-
PUT 5	3⊕5=6	-	{6:1}	-
LOOK	6	2	{6:2}	1

2回目の LOOK では XOR 値が 6 で、辞書に {6:1} があるので答えは 1 となります。その後辞書を {6:2} に更新します。

アルゴリズム

1. 変数 xor_val = 0 と空のスタック stack を用意する
2. 辞書 last_seen（XOR 値 → 最後にその値が現れた LOOK 番号）を用意する
3. 各操作について：
   • PUT c: スタックに \(c\) を積み、xor_val ^= c
   • REMOVE: スタックの先頭を取り出し、xor_val ^= (取り出した値)
   • LOOK:
     • LOOK カウンタを1増やす
     • xor_val が last_seen にあれば、その番号を出力。なければ \(-1\) を出力
     • last_seen[xor_val] を現在の LOOK 番号で更新

計算量

• 時間計算量: \(O(N)\) — 各操作は \(O(1)\) で処理され、全体で \(N\) 回の操作を行う
• 空間計算量: \(O(N)\) — スタックと辞書にそれぞれ最大 \(O(N)\) の要素が格納される

実装のポイント

• XOR の性質 \(a \oplus a = 0\) により、同じ値を2回 XOR すると打ち消し合う。これを利用して REMOVE 時に xor_val ^= top とするだけで正しく更新できる

• last_seen 辞書は LOOK のたびに 上書き する（最大の \(j\) を求めるので、常に最新の番号だけ保持すればよい）

• 入力が大量になる可能性があるため、sys.stdin.readline を使って高速に読み込む

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    stack = []
    xor_val = 0  # current XOR of all cards in the stack
    # For each LOOK, we need the XOR value, then find the last previous LOOK with same value
    # We'll use a dictionary mapping xor_value -> last LOOK index (1-based among LOOKs)
    last_seen = {}  # xor_value -> last LOOK index
    results = []
    look_count = 0
    
    for _ in range(N):
        line = input().strip()
        if line.startswith("PUT"):
            c = int(line.split()[1])
            stack.append(c)
            xor_val ^= c
        elif line == "REMOVE":
            top = stack.pop()
            xor_val ^= top
        else:  # LOOK
            look_count += 1
            v = xor_val
            if v in last_seen:
                results.append(str(last_seen[v]))
            else:
                results.append("-1")
            last_seen[v] = look_count
    
    sys.stdout.write("\n".join(results) + "\n")

main()

---

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