P6864 [RC-03] Memory

Little W wants to write a background story about memory, but he forgot it.

There is a bracket string $S$. Initially, $S$ contains only one pair of brackets (that is, the initial $S$ is `()`). Then there are $n$ operations of three types: 1. Append one pair of brackets to the end of the current $S$ (that is, $S$ becomes `S()`); 2. Add one pair of brackets around the outside of the current $S$ (that is, $S$ becomes `(S)`); 3. Cancel the $x$-th operation, i.e., remove **all effects** caused by the $x$-th operation (for example, if the $x$-th operation is also a cancel operation and it canceled the $y$-th operation, then the essence of the current operation is to restore the effect of the $y$-th operation). After each operation, you need to output the number of non-empty substrings (substrings must be contiguous) of $S$ that can be matched as brackets. A bracket string can be matched if and only if the numbers of left and right brackets are equal, and in every prefix, the number of left brackets is not less than the number of right brackets.

The first line: an integer $n$, the number of operations. The next $n$ lines: each line starts with an integer $op$, indicating the type of the operation: If $op=1$, it means operation $1$ is performed. If $op=2$, it means operation $2$ is performed. If $op=3$, there is also an integer $x$ afterwards, meaning operation $3$ is performed and the $x$-th operation is canceled (operations are numbered from $1$ to $n$, and it is guaranteed that the $x$-th operation has already happened). Note that a cancel operation **does not affect any operation indices**. Indices depend only on the input order.

Output $n$ lines in total. On line $i$, output an integer $ans_i$, the number of non-empty substrings of the whole bracket string that can be matched after the $i$-th operation ends.

[Sample $1$ Explanation] Use $S[i,j]$ to denote the substring from $S_i$ to $S_j$ (indices start from $1$). Initially, $S$ is `()`. After each operation: After the $1$-st operation: $S$ is `()()`. The matched substrings are $S[1,2]$, $S[1,4]$, and $S[3,4]$, for a total of $3$. After the $2$-nd operation: $S$ is `(()())`. The matched substrings are $S[1,6]$, $S[2,3]$, $S[2,5]$, and $S[4,5]$, for a total of $4$. After the $3$-rd operation: $S$ is `(())`. The matched substrings are $S[1,4]$ and $S[2,3]$, for a total of $2$. After the $4$-th operation: $S$ is `(())()`. The matched substrings are $S[1,4]$, $S[1,6]$, $S[2,3]$, and $S[5,6]$, for a total of $4$. After the $5$-th operation: $S$ is `(()())()`. The matched substrings are $S[1,6]$, $S[1,8]$, $S[2,3]$, $S[2,5]$, $S[4,5]$, and $S[7,8]$, for a total of $6$. After the $6$-th operation: $S$ is `(())()`. The matched substrings are $S[1,4]$, $S[1,6]$, $S[2,3]$, and $S[5,6]$, for a total of $4$. --- [Constraints] **This problem uses bundled testdata.** For all data: $1\leq n\leq 2\times 10^5$, $op\in \{1,2,3\}$, $1\leq x\leq n$. Each operation can be canceled at most once in form (i.e., all $x$ are distinct). | Subtask ID | $n\leq$ | $op\in$ | Score | | :--------: | :------------: | :---------: | :---: | | Subtask 1 | $100$ | $\{1,2,3\}$ | $10$ | | Subtask 2 | $10^3$ | $\{1,2,3\}$ | $10$ | | Subtask 3 | $10^5$ | $\{1,2,3\}$ | $30$ | | Subtask 4 | $2\times 10^5$ | $\{1,2\}$ | $20$ | | Subtask 5 | $2\times 10^5$ | $\{1,2,3\}$ | $30$ | Translated by ChatGPT 5