AT_abc428_c.[ABC428C] Brackets Stack Query

当且仅当字符串 $T$ 满足以下条件时，被称为“好括号序列”：

• $T$ 可以通过重复以下操作零次或多次变成空字符串：
  • 选择 $T$ 中包含的子串 ()，并将其删除。

例如，(), (()()) 以及空字符串都是好括号序列，而 )()( 和 ))) 不是好括号序列。

现在有一个字符串 $S$，初始时 $S$ 为空字符串。依次处理 $Q$ 个查询。每次查询后，判断 $S$ 当前是否为好括号序列。查询有以下两种类型：

• 1 c：给定一个字符 $c$，$c$ 只可能是 ( 或 )。将 $c$ 添加到 $S$ 的末尾。
• 2：删除 $S$ 的最后一个字符。保证此时 $S$ 不为空。

输入按如下格式从标准输入给出，其中 $\mathrm{query}_i$ 表示第 $i$ 次查询。

$Q$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$

每个查询有以下两种格式之一：

$1\ c$

$2$

输出共 $Q$ 行。第 $i$ 行输出在处理完第 $i$ 次查询后 $S$ 是否为好括号序列：若是输出 Yes，否则输出 No。

样例解释 1

第 $1$ 次查询后 $S$ 为 (，不是好括号序列。
第 $2$ 次查询后 $S$ 为空字符串，是好括号序列。
第 $3$ 次查询后 $S$ 为 (，不是好括号序列。
第 $4$ 次查询后 $S$ 为 ()，是好括号序列。
第 $5$ 次查询后 $S$ 为 (，不是好括号序列。
第 $6$ 次查询后 $S$ 为 ((，不是好括号序列。
第 $7$ 次查询后 $S$ 为 (()，不是好括号序列。
第 $8$ 次查询后 $S$ 为 (())，是好括号序列。

数据范围

• $1 \leq Q \leq 8 \times 10^5$
• 类型 $1$ 查询中的 $c$ 仅为 ( 或 )。
• 保证类型 $2$ 查询时 $S$ 非空。
• $Q$ 为整数。

由 ChatGPT 5 翻译