XOR の性質により、以下のことがいえます。

• 元の総 XOR を \(x\) とする。
• 山に \(c\) が書かれたカードを追加すると、総 XOR は \(x\ {\rm XOR}\ c\) となる。
• 山から \(c\) が書かれたカードを削除しても、総 XOR は \(x\ {\rm XOR}\ c\) となる。

前者は当たり前ですが、後者は何故成り立つのでしょうか？

山のうち \(c\) 以外のカードの総 XOR を \(x'\) とします。このとき、現在の山の総 XOR は \(x'\ {\rm XOR}\ c\) です。
ここから \(c\) を取り除くとき、総 XOR は \(x'\) となります。
ここで、総 XOR は \(x\ {\rm XOR}\ c\) で得られます。
なぜなら、 XOR の性質から \(x\ {\rm XOR}\ c = (x'\ {\rm XOR}\ c)\ {\rm XOR}\ c = x'\ {\rm XOR}\ (c \ {\rm XOR}\ c)=x'\ {\rm XOR}\ 0=x'\) が成り立つからです。

ここが分かれば、あとは問題文の指示に従って実装すればよいです。

カードの山を stack というデータ構造で持つとよいです。

stack は以下のことが行えます。本を積み上げた山などに例えられることがあります。

• 値を追加する
• 残っている中で直近に追加された値を調べる
• 残っている中で直近に追加された値を削除する

この stack を使うと、以下のように実装できます。

• stack \(s\) と全体の総 XOR を保持する変数 \(x\) を用意する。
• PUT \(c\) は、 \(c\) を stack に追加して \(x\) を \(x\ {\rm XOR}\ c\) で更新すると実現可能です。
• REMOVE は、 stack からひとつ要素を削除し、削除された要素を \(y\) として \(x\) を \(x\ {\rm XOR}\ y\) で更新すると実現可能です。
• LOOK は、例えば連想配列を用いて以下の情報を保持しておくことで実現可能です。
  • \(mp[x] = \{\) 直近で値が \(x\) であるような LOOK が行われたのはいつか？ \(\}\)
  • \(x\) が \(2^{30}-1\) 程度まで大きくなるので、普通の配列では不十分であることに注意してください。ただし、連想配列は多くの言語で標準で実装されています。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N;
  cin >> N;
  stack<int> pile;
  map<int,int> his;
  int x=0;
  int clock=0;
  while(N--){
    string typ;
    cin >> typ;
    if(typ[0]=='P'){
      int c;
      cin >> c;
      pile.push(c);
      x^=c;
    }
    else if(typ[0]=='R'){
      x^=pile.top();
      pile.pop();
    }
    else{
      clock++;
      auto it=his.find(x);
      if(it==his.end()){cout << "-1\n";}
      else{cout << (*it).second << "\n";}
      his[x]=clock;
    }
  }
  return 0;
}