← 返回题目列表

Codeforces · 1858/E1

E1. 回滚(简单版)

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

这是这个问题的简单版本。这些版本之间的唯一区别是您必须以在线模式解决困难版本。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

你有一个数组 $$$a$$$,它最初是空的。您需要处理以下类型的查询:

- + $$$x$$$ — 将整数 $$$x$$$ 添加到数组 $$$a$$$ 的末尾。
- - $$$k$$$ — 从数组 $$$a$$$ 中删除最后的 $$$k$$$ 数字。
- ! — 回滚最后一个活动更改(即,使数组 $$$a$$$ 恢复为更改之前的状态)。在这个问题中,只有前两种类型(+和-)的查询被视为更改。
- ? — 找出数组 $$$a$$$ 中不同数字的数量。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 10^6$$$) — 查询数。

接下来的 $$$q$$$ 行包含如上所述的查询。

保证

- 在第一类查询中,$$$1 \le x \le 10^6$$$;
- 在第二类查询中,$$$k \ge 1$$$ 和 $$$k$$$ 不超过数组 $$$a$$$ 的当前长度;
-在第三类型查询时,至少有一个第一或第二类型查询可以回滚。

还保证第四类(?)的查询次数不超过$$$10^5$$$。

输出

对于第四种类型的每个查询,输出一个整数 - 查询时数组 $$$a$$$ 中不同元素的数量。

示例

输入 #1

10
+ 1
+ 2
+ 2
?
!
+ 3
- 2
?
+ 1
?

输出 #1

2
1
1

输入 #2

6
+ 1
+ 1000000
?
!
!
?

输出 #2

2
0

注意

在第一个示例数组 $$$a$$$ 中更改如下:

1. 第一次查询后,$$$a=[1]$$$。
2. 第二次查询后,$$$a=[1,2]$$$。
3. 第三次查询后,$$$a=[1,2,2]$$$。
4. 在第四次查询时,数组$$$a$$$中有$$$2$$$不同的整数:$$$1$$$和$$$2$$$。
5. 第五次查询后,$$$a=[1,2]$$$(回滚更改 + 2)。
6. 第六次查询后,$$$a=[1,2,3]$$$。
7. 第七次查询后,$$$a=[1]$$$。
8. 在第八次查询时,数组$$$a$$$中只有一个$$$1$$$。
9. 第九次查询后,$$$a=[1,1]$$$。
10. 在第十次查询的时刻,数组$$$a$$$中只有两个$$$1$$$。

在第二个示例数组 $$$a$$$ 中更改如下:

1. 第一次查询后,$$$a=[1]$$$。
2. 第二次查询后,$$$a=[1,1\,000\,000]$$$。
3. 在第三次查询时,数组$$$a$$$中有$$$2$$$不同的整数:$$$1$$$和$$$1\,000\,000$$$。
4. 第四次查询后,$$$a=[1]$$$(回滚更改+1000000)。
5. 第五次查询后,$$$a=[]$$$(回滚更改 + 1)。
6. 在第六次查询时,数组 $$$a$$$ 中没有整数,因此该查询的答案是 $$$0$$$。