Rollbacks (Easy Version) (Codeforces 1858E1)
Tags: Others, trees

This is an easy 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: 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$$$.

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

Note: In the first example array $$$a$$$ changes as follows:   After the first query, $$$a=[1]$$$.  After the second query, $$$a=[1,2]$$$.  After the third query, $$$a=[1,2,2]$$$.  At the moment of the fourth query, there are $$$2$$$ distinct intergers in the array $$$a$$$: $$$1$$$ and $$$2$$$.  After the fifth query, $$$a=[1,2]$$$ (rolled back the change + 2).  After the sixth query, $$$a=[1,2,3]$$$.  After the seventh query, $$$a=[1]$$$.  At the moment of the eigth query, there is only one $$$1$$$ in the array $$$a$$$.  After the ninth query, $$$a=[1,1]$$$.  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:   After the first query, $$$a=[1]$$$.  After the second query, $$$a=[1,1\,000\,000]$$$.  At the moment of the third query, there are $$$2$$$ distinct intergers in the array $$$a$$$: $$$1$$$ and $$$1\,000\,000$$$.  After the fourth query, $$$a=[1]$$$ (rolled back the change + 1000000).  After the fifth query, $$$a=[]$$$ (rolled back the change + 1).  At the moment of the sixth query, there are no integers in the array $$$a$$$, so the answer to this query is $$$0$$$. 

Sample Inputs:
10
+ 1
+ 2
+ 2
?
!
+ 3
- 2
?
+ 1
?

6
+ 1
+ 1000000
?
!
!
?

Sample Outputs:
2
1
1

2
0

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * (q + 1) + v

def make_graph(n, m):
    (x, s) = ([0] * (2 * m), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        (u, v) = (parent[(i >> 1) + 1], (i >> 1) + 1)
        s[u + 2] += 1
        (x[i], x[i + 1]) = (u, v)
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)
q = int(input())
(u, m) = (0, 0)
st = [0]
parent = [-1] * (20 * (q + 1))
a = [0] * (q + 1)
pow2 = [1]
for _ in range(20):
    pow2.append(2 * pow2[-1])
q0 = []
for _ in range(q):
    t = list(input().rstrip().decode().split())
    if t[0] == '+':
        x = int(t[1])
        m += 1
        (a[m], parent[m]) = (x, u)
        st.append(m)
        for i in range(20):
            p = parent[f(i, u)]
            if p == -1:
                break
            parent[f(i + 1, m)] = p
            u = p
        u = m
    elif t[0] == '-':
        k = int(t[1])
        for i in range(20):
            if k & pow2[i]:
                k ^= pow2[i]
                u = parent[f(i, u)]
            if not k:
                break
        st.append(u)
    elif t[0] == '!':
        st.pop()
        u = st[-1]
    else:
        q0.append(u)
n = m + 1
(G, s0) = make_graph(n, m)
st = [0]
now = list(s0)
c = [0] * (max(a) + 5)
ans0 = [0] * (n + 1)
ans1 = 0
while st:
    i = st[-1]
    if now[i] < s0[i + 1]:
        j = G[now[i]]
        if not c[a[j]]:
            c[a[j]] = j
            ans1 += 1
        ans0[j] = ans1
        st.append(j)
        now[i] += 1
    else:
        if c[a[i]] == i:
            c[a[i]] = 0
            ans1 -= 1
        st.pop()
ans = [ans0[i] for i in q0]
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
from io import BytesIO, IOBase
import sys
import os
import bisect
import math
import random
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations, count, product
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
BUFSIZE = 5096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
N = 1 << 20
q = II()
pos = [q] * N
n = 0
a = []
b = [0] * q
c = [0] * (q + 1)
c[q] = n
s = [0] * (q + 1)
for _ in range(q):
    o = I()
    if o[0] == '+':
        x = int(o[1:])
        a.append([x, pos[x], b[n], pos[b[n]], s[n + 1]])
        if pos[b[n]] == n:
            c[pos[b[n]]] -= 1
            pos[b[n]] = q
            c[pos[b[n]]] += 1
        if pos[x] > n:
            c[pos[x]] -= 1
            pos[x] = n
            c[pos[x]] += 1
        s[n + 1] = s[n] + c[n]
        b[n] = x
        n += 1
    elif o[0] == '-':
        k = int(o[1:])
        n -= k
        a.append([-1, k])
    elif o == '?':
        ans = s[n]
        print(ans)
    else:
        tmp = a.pop()
        if tmp[0] == -1:
            n += tmp[1]
        else:
            (x, y, z, w, t) = tmp
            n -= 1
            b[n] = z
            s[n + 1] = t
            if pos[x] != y:
                c[pos[x]] -= 1
                pos[x] = y
                c[pos[x]] += 1
            if pos[z] != w:
                c[pos[z]] -= 1
                pos[z] = w
                c[pos[z]] += 1

Solution (Python):
import math
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
import heapq
BUFSIZE = 1048576

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ans = [-1 for i in range(1000005)]
pos = [0 for i in range(1000005)]
pre = [0 for i in range(1000005)]
lenat = [0 for i in range(1000005)]
lst = [0 for i in range(1000005)]
fa = [0 for i in range(1000005)]
v = [0 for i in range(1000005)]
nds = [[] for i in range(1000005)]
g = [[] for i in range(1000005)]
changes1 = [0 for i in range(1000005)]
changes2 = [0 for i in range(1000005)]
at = 0
len = 0
tot = 0
q = int(input())
for _ in range(1, q + 1):
    tmp = list(input().split())
    op = tmp[0]
    if op == '+':
        x = int(tmp[1])
        tot += 1
        len += 1
        changes1[_] = len + 1
        changes2[_] = pos[len]
        pos[len] = tot
        v[tot] = x
        lst[_] = tot
        fa[tot] = lst[at]
        g[lst[at]].append(tot)
        pre[_] = at
        at = _
        lenat[at] = len
    if op == '-':
        k = int(tmp[1])
        lst[_] = pos[len - k]
        len -= k
        pre[_] = at
        at = _
        lenat[at] = len
    if op == '!':
        if changes1[at] > 0:
            pos[changes1[at] - 1] = changes2[at]
        at = pre[at]
        len = lenat[at]
    if op == '?':
        nds[lst[at]].append(_)
R = 0
s = 0
for i in range(1000005):
    lenat[i] = 0
    pos[i] = 0
while R >= 0:
    x = lenat[R]
    R -= 1
    if x <= 2000000:
        if v[x] != 0:
            if pos[v[x]] == 0:
                s += 1
            pos[v[x]] += 1
        for i in nds[x]:
            ans[i] = s
        lenat[R + 1] = x + 4000000
        R += 1
        for i in g[x]:
            lenat[R + 1] = i
            R += 1
    else:
        x -= 4000000
        if v[x] != 0:
            if pos[v[x]] == 1:
                s -= 1
            pos[v[x]] -= 1
for i in range(q + 1):
    if ans[i] != -1:
        print(ans[i])