Rollbacks (Hard Version)
Contest: Codeforces Round 893 (Div. 2)
Difficulty rating: 2600
Tags: data structures, interactive, trees

This is a hard version of this problem. The only difference between the versions is that you have to solve the hard version in online mode. You can make hacks only if both versions of the problem are solved.

You have an array $$$a$$$, which is initially empty. You need to process queries of the following types:

- + $$$x$$$ — add the integer $$$x$$$ to the end of the array $$$a$$$.
- - $$$k$$$ — remove the last $$$k$$$ numbers from the array $$$a$$$.
- ! — roll back the last active change (i.e., make the array $$$a$$$ the way it was before the change). In this problem, only queries of the first two types (+ and -) are considered as changes.
- ? — find the number of distinct numbers in the array $$$a$$$.

Input format:
The first line contains an integer $$$q$$$ ($$$1 \leq q \leq 10^6$$$) — the number of queries.

The next $$$q$$$ lines contain the queries as described above.

It is guaranteed that

- in the queries of the first type, $$$1 \le x \le 10^6$$$;
- in the queries of the second type, $$$k \ge 1$$$ and $$$k$$$ does not exceed the current length of the array $$$a$$$;
- at the moment of the queries of the third type, there is at least one query of the first or of the second type that can be rolled back.

It is also guaranteed that the number of queries of the fourth type (?) does not exceed $$$10^5$$$.

Note that you should solve the problem in online mode. It means that you can't read the whole input at once. You can read each query only after writing the answer for the last query, so don't forget to flush output after printing answers. You can use functions like fflush(stdout) in C++ and BufferedWriter.flush in Java or similar after each writing in your program.

Output format:
For each query of the fourth type output one integer — the number of distinct elements in array $$$a$$$ at the moment of query.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example array $$$a$$$ changes as follows:

1. After the first query, $$$a=[1]$$$.
2. After the second query, $$$a=[1,2]$$$.
3. After the third query, $$$a=[1,2,2]$$$.
4. At the moment of the fourth query, there are $$$2$$$ distinct intergers in the array $$$a$$$: $$$1$$$ and $$$2$$$.
5. After the fifth query, $$$a=[1,2]$$$ (rolled back the change + 2).
6. After the sixth query, $$$a=[1,2,3]$$$.
7. After the seventh query, $$$a=[1]$$$.
8. At the moment of the eigth query, there is only one $$$1$$$ in the array $$$a$$$.
9. After the ninth query, $$$a=[1,1]$$$.
10. At the moment of the tenth query, there are only two $$$1$$$ in the array $$$a$$$.

In the second example array $$$a$$$ changes as follows:

1. After the first query, $$$a=[1]$$$.
2. After the second query, $$$a=[1, 1\,000\,000]$$$.
3. At the moment of the third query, there are $$$2$$$ distinct intergers in the array $$$a$$$: $$$1$$$ and $$$1\,000\,000$$$.
4. After the fourth query, $$$a=[1]$$$ (rolled back the change + 1000000).
5. After the fifth query, $$$a=[]$$$ (rolled back the change + 1).
6. At the moment of the sixth query, there are no integers in the array $$$a$$$, so the answer to this query is $$$0$$$.

Example input:
10
+ 1
+ 2
+ 2
?
!
+ 3
- 2
?
+ 1
?

Example output:
2
1
1

Example input:
6
+ 1
+ 1000000
?
!
!
?

Example output:
2
0

Editorial:
First, let's learn how to solve the problem without rollbacks. Let $$$b$$$ be an array of the same length as $$$a$$$, where $$$b_i=1$$$ if $$$i$$$ is the minimum position at which the number $$$a_i$$$ is in the array $$$a$$$, and $$$b_i=0$$$ otherwise. Then the number of different numbers in the array $$$a$$$ is equal to the sum of all the elements of the array $$$b$$$.
The $$$b$$$ array can be maintained using a Fenwick tree, a segment tree, or any other data structure that supports point updates and range sum queries. The author's solution uses the Fenwick tree.
Let's use the method that is often used when implementing a stack or a deque: we create a large array $$$A$$$ and at each moment we store the index of the last "existing" element $$$r$$$ (this is just the size of the array $$$a$$$ at this moment). The array $$$a$$$ itself will be a prefix of $$$A$$$, that is, $$$a_{i}=A_{i}$$$ for $$$i\leq len(a)$$$. Also, for each value $$$val$$$ we maintain std::set of indexes on which the $$$val$$$ value is located in the $$$A$$$ array (in $$$A$$$, not in $$$a$$$).
Then for the operation of removing $$$k$$$ elements from the end of the array $$$a$$$, it is enough to reduce the value of the index $$$r$$$ by $$$k$$$. This operation works in $$$O(1)$$$.
When adding one element $$$x$$$ to the end of the array, we need to check if it has been encountered before, and change one element in the Fenwick tree accordingly. This can be done in $$$O(\log{q})$$$ using std::set for the corresponding value. You also need to increase $$$r$$$ by 1, assign $$$A_{r} =x$$$ after that, and update the corresponding std::set. This operation works for $$$O(\log{q})$$$.
In order to find the number of different numbers in $$$a$$$, we need to find the sum in the Fenwick tree on the prefix of length $$$r$$$ in the array $$$b$$$. This operation works in $$$O(\log{q})$$$.
Now, we need to learn how to roll back operations. Note that we perform the deletion operation in $$$O(1)$$$, and the addition operation in $$$O(\log{q})$$$, so we can roll back these operations with the same asymptotics. We can just store a stack of all changes, and remember everything that we changed during the operations.
The final asymptotics is $$$O(q\log{q})$$$.