← 返回题目列表

AtCoder · awc0050_c

C. 堆叠卡

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥喜欢纸牌游戏,他会把写有数字的卡片堆放在桌子上。

每张卡片上都写有一个正整数。高桥通过堆叠卡片来堆积卡片。当放置一张新牌时,他将其放在一堆牌的顶部,而当取出一张牌时,他只能拿最上面的一张(最近放置的一张)。取出的卡牌将被丢弃,不参与任何后续操作。

最初,这堆牌不包含任何牌。高桥表演 N 操作按顺序进行。每个操作都是以下三种类型之一:

  • 放置操作 PUT c:放置正整数的卡片 c 写在堆的顶部。
  • 删除操作 REMOVE:从牌堆中取出最上面的牌并将其丢弃。执行此操作时,保证该堆中至少包含一张牌。
  • 查看操作 LOOK:计算 按位异或 (异或)当前堆中所有卡片上写的数字。执行此操作时,保证该堆中至少包含一张牌。如果这堆牌恰好包含一张牌,则 XOR 值就是该牌本身上写的数字。

仅从 N 操作按出现的顺序排列,并编号 1, 2, 3, \ldots, K (其中 K 是查找操作的总数)。让 v_i 为 XOR 值 i第一次查看操作。

对于每个 i = 1, 2, \ldots, K,找到最大的整数 j 这样 v_j = v_i 和 j < i。换句话说,找到最近的过去查找操作的数量,该操作产生与 i第一次查看操作。如果没有这样的 j 存在,输出 -1.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 值 每个 put 操作中给出的 c 满足 1 \leq c \leq 10^9.
  • 当 执行 REMOVE 操作后,该堆至少包含一张牌。
  • 当 执行 LOOK 操作后,该堆至少包含一张牌。
  • 其中 N 操作,至少一项 包括 LOOK 操作(即, K \geq 1).
  • 输入中给出的所有数值均为整数。

输入

输入由标准输入给出,格式如下:

N
\mathrm{event}_1
\mathrm{event}_2
\vdots
\mathrm{event}_N
  • 第一行包含一个整数 N 代表操作总数。
  • 以下内容中 N 行, i-第行包含 i第次操作 \mathrm{event}_i 采用以下格式之一:
  • 对于放置操作: PUT c (字符串 PUT 后跟一个正整数 c 以空格分隔)
  • 对于删除操作: REMOVE
  • 对于查看操作: LOOK

输出

让 K 是查找操作的总数。输出 K 行。

关于 i第行 (1 \leq i \leq K),让 v_i 为 XOR 值 i第一次查找操作,并输出最大的整数 j 这样 v_j = v_i 和 j < i。如果没有这样的 j 存在,输出 -1.


示例输入 1

7
PUT 3
PUT 5
LOOK
PUT 6
LOOK
REMOVE
LOOK

示例输出 1

-1
-1
1

示例输入 2

6
PUT 1
LOOK
PUT 2
LOOK
PUT 4
LOOK

示例输出 2

-1
-1
-1

示例输入 3

15
PUT 10
PUT 7
LOOK
REMOVE
LOOK
PUT 3
LOOK
PUT 9
LOOK
REMOVE
REMOVE
LOOK
PUT 5
LOOK
REMOVE

示例输出 3

-1
-1
-1
-1
2
-1

示例输入 4

24
PUT 1
PUT 2
PUT 4
LOOK
REMOVE
LOOK
REMOVE
LOOK
PUT 8
LOOK
PUT 6
LOOK
REMOVE
LOOK
REMOVE
LOOK
PUT 3
LOOK
PUT 2
LOOK
REMOVE
LOOK
REMOVE
LOOK

示例输出 4

-1
-1
-1
-1
-1
4
3
-1
-1
8
7

示例输入 5

2
PUT 1000000000
LOOK

示例输出 5

-1