[RC-03] 记忆
题目背景
小 W 想写一个关于记忆的题目背景,但是他忘记了。
题目描述
有一个括号串 $S$,一开始 $S$ 中只包含一对括号(即初始的 $S$ 为 `()`),接下来有 $n$ 个操作,操作分为三种:
1. 在当前 $S$ 的末尾加一对括号(即 $S$ 变为 `S()`);
2. 在当前 $S$ 的最外面加一对括号(即 $S$ 变为 `(S)`);
3. 取消第 $x$ 个操作,即去除第 $x$ 个操作造成过的**一切影响**(例如,如果第 $x$ 个操作也是取消操作,且取消了第 $y$ 个操作,那么当前操作的实质就是恢复了第 $y$ 个操作的作用效果)。
每次操作后,你需要输出 $S$ 的能够括号匹配的非空子串(子串要求连续)个数。
一个括号串能够括号匹配,当且仅当其左右括号数量相等,且任意一个前缀中左括号数量不少于右括号数量。
输入输出格式
输入格式
第一行:一个整数 $n$,表示操作的个数。
接下来 $n$ 行:每行先有一个整数 $op$,表示操作的种类:
若 $op=1$,则表示执行了操作 $1$;
若 $op=2$,则表示执行了操作 $2$;
若 $op=3$,接下来还有一个整数 $x$,表示执行操作 $3$,取消了第 $x$ 个操作(操作按 $1$ 到 $n$ 编号,保证第 $x$ 个操作已发生),注意取消操作**并不影响任何操作的编号**,编号只取决于输入顺序。
输出格式
共 $n$ 行:第 $i$ 行输出一个整数 $ans_i$,表示第 $i$ 次操作结束后整个括号串的括号匹配的非空子串个数。
输入输出样例
输入样例 #1
6
1
2
3 1
1
3 3
3 5
输出样例 #1
3
4
2
4
6
4
输入样例 #2
10
1
2
2
3 2
1
3 3
3 6
1
2
1
输出样例 #2
3
4
5
4
6
6
6
9
10
12
说明
【样例 $1$ 解释】
用 $S[i,j]$ 表示从 $S_i$ 到 $S_j$ 的子串(下标从 $1$ 开始)。
一开始 $S$ 为 `()`,每次操作后:
第 $1$ 次操作后:$S$ 为 `()()`,匹配的子串有 $S[1,2]$,$S[1,4]$ 和 $S[3,4]$,共 $3$ 个。
第 $2$ 次操作后:$S$ 为 `(()())`,匹配的子串有 $S[1,6]$,$S[2,3]$,$S[2,5]$ 和 $S[4,5]$,共 $4$ 个。
第 $3$ 次操作后:$S$ 为 `(())`,匹配的子串有 $S[1,4]$ 和 $S[2,3]$,共 $2$ 个。
第 $4$ 次操作后:$S$ 为 `(())()`,匹配的子串有 $S[1,4]$,$S[1,6]$,$S[2,3]$ 和 $S[5,6]$,共 $4$ 个。
第 $5$ 次操作后:$S$ 为 `(()())()`,匹配的子串有 $S[1,6]$,$S[1,8]$,$S[2,3]$,$S[2,5]$,$S[4,5]$ 和 $S[7,8]$,共 $6$ 个。
第 $6$ 次操作后:$S$ 为 `(())()`,匹配的子串有 $S[1,4]$,$S[1,6]$,$S[2,3]$ 和 $S[5,6]$,共 $4$ 个。
---
【数据范围】
**本题采用捆绑测试。**
对于全部数据:$1\leq n\leq 2\times 10^5$,$op\in \{1,2,3\}$,$1\leq x\leq n$,一个操作在形式上最多只会被取消一次(即所有 $x$ 互不相同)。
| 子任务编号 | $n\leq$ | $op\in$ | 分值 |
| :--------: | :------------: | :---------: | :--: |
| 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$ |