这是这个问题的困难版本。这些版本之间的唯一区别是您必须以在线模式解决困难版本。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
你有一个数组 $$$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$$$。
请注意,您应该以在线模式解决该问题。这意味着您无法一次读取整个输入。您只能在编写最后一个查询的答案后才能读取每个查询,因此不要忘记在打印答案后刷新输出。每次编写程序后,您可以使用 C++ 中的 fflush(stdout) 和 Java 中的 BufferedWriter.flush 等函数或类似函数。
输出
对于第四种类型的每个查询,输出一个整数 - 查询时数组 $$$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$$$。