分数: 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