P6864 [RC-03] 记忆

小 W 想写一个关于记忆的题目背景，但是他忘记了。

有一个括号串 $S$，一开始 $S$ 中只包含一对括号（即初始的 $S$ 为 `()`），接下来有 $n$ 个操作，操作分为三种： 1. 在当前 $S$ 的末尾加一对括号（即 $S$ 变为 `S()`）； 2. 在当前 $S$ 的最外面加一对括号（即 $S$ 变为 `(S)`）； 3. 取消第 $x$ 个操作，即去除第 $x$ 个操作造成过的**一切影响**（例如，如果第 $x$ 个操作也是取消操作，且取消了第 $y$ 个操作，那么当前操作的实质就是恢复了第 $y$ 个操作的作用效果）。 每次操作后，你需要输出 $S$ 的能够括号匹配的非空子串（子串要求连续）个数。 一个括号串能够括号匹配，当且仅当其左右括号数量相等，且任意一个前缀中左括号数量不少于右括号数量。

无

无

【样例 $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$ |