Overview

This problem requires managing the “bitwise XOR (exclusive or) of all elements” that changes according to the state of a stack (pile), and for each check operation, identifying the most recent timing when the same XOR value appeared in the past.

Analysis

1. Utilizing Properties of XOR

If we compute the “XOR sum of all cards currently in the pile” from scratch every time, with \(M\) being the number of cards in the pile, a single LOOK operation would take \(O(M)\). In the worst case, \(M\) is proportional to \(N\), making the overall time complexity \(O(N^2)\), which will not meet the time limit.

However, XOR has the important property that “XORing the same value twice returns to the original value (\(A \oplus B \oplus B = A\))”. Using this, we can efficiently update the current XOR sum as follows: - PUT c: XOR the current XOR sum with \(c\). - REMOVE: Let \(v\) be the value on top of the pile; XOR the current XOR sum with \(v\) (this cancels out the effect of \(v\)).

This allows each operation to be processed in \(O(1)\).

2. Quickly Finding the Most Recent Same Value

For the XOR value obtained at each LOOK operation, we need to record “when the same value appeared in the past.” An associative array (Python dictionary) is ideal for this. - Key: XOR values that have appeared so far - Value: The LOOK operation number when that XOR value last appeared

Each time a LOOK operation is performed, we retrieve the number corresponding to the current XOR value from the dictionary, and then update the dictionary value to the current operation number. This way, we can always obtain the “most recent number.”

Algorithm

1. Data Preparation:
   • A stack (list) to manage card values
   • A variable current_xor to hold the current XOR total (initial value 0)
   • A dictionary last_seen to associate XOR values with LOOK numbers
   • A variable look_count to count the number of LOOK operations
2. Processing Each Operation:
   • PUT c: Push \(c\) onto the stack and perform current_xor ^= c.
   • REMOVE: pop a value from the stack and XOR that value with current_xor.
   • LOOK:
     1. Increment look_count.
     2. If current_xor exists in last_seen, record that value; otherwise, record -1.
     3. Update last_seen[current_xor] with the current look_count.
3. Output Results: Output the recorded results in order.

Complexity

• Time Complexity: \(O(N)\)
  • Each operation (PUT, REMOVE, LOOK) is processed in amortized \(O(1)\), including stack operations and dictionary reads/writes. Since the number of operations is \(N\), the overall complexity is \(O(N)\).
• Space Complexity: \(O(N)\)
  • The sizes of the stack, dictionary, and result list are all proportional to at most \(N\).

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), in Python, using sys.stdin.read().split() to read all input at once instead of input(), and using sys.stdout.write() for bulk output, can significantly reduce execution time.

• Initial Value: Since the identity element of XOR is \(0\), the initial value of current_xor is set to \(0\). However, according to the problem constraints, there is always at least one card when LOOK is performed, so the XOR value of an empty state will never be referenced.

  Source Code

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

This editorial was generated by gemini-3-flash-thinking.