CF1858E2 Rollbacks (Hard Version)

这是该问题的困难版本。唯一的区别在于你需要以在线模式解决困难版本。只有当两个版本都被解决时，你才能进行 hack。 你有一个初始为空的数组 $a$。你需要处理以下几种类型的操作： - ```+ x``` —— 将整数 $x$ 添加到数组 $a$ 的末尾。 - ```- k``` —— 从数组 $a$ 的末尾移除最后 $k$ 个数。 - ```!``` —— 撤销上一次有效的更改（即，使数组 $a$ 恢复到更改前的状态）。在本题中，只有前两种类型（+ 和 -）的操作被视为更改。 - ```?``` —— 查询当前数组 $a$ 中不同数字的个数。

第一行包含一个整数 $q$（$1 \leq q \leq 10^6$），表示操作的数量。 接下来的 $q$ 行，每行包含一个如上所述的操作。 保证： - 对于第一种操作，$1 \leq x \leq 10^6$； - 对于第二种操作，$k \geq 1$ 且 $k$ 不超过当前数组 $a$ 的长度； - 对于第三种操作，至少存在一个可以被撤销的第一或第二种操作； - 第四种操作（?）的总次数不超过 $10^5$。 注意，你需要以在线模式解决本题。这意味着你不能一次性读取全部输入。你只能在输出上一个查询的答案后读取下一个操作，因此在输出答案后不要忘记刷新输出缓冲区。在 C++ 中可以使用 fflush(stdout)，在 Java 中可以使用 BufferedWriter.flush，或在你的编程语言中使用类似方法。

对于每个第四种类型的操作，输出一个整数，表示当前数组 $a$ 中不同元素的个数。

在第一个样例中，数组 $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$。 由 ChatGPT 4.1 翻译