分数: 300 点
问题陈述
一个字符串 T 满足以下条件时,才称为良好的括号序列: 通过重复以下操作零次或多次,可以将
-
T 变成空字符串:
- 选择
()包含在 T 作为(连续)子字符串并将其删除。
- 选择
例如, (), (()())和空字符串是很好的括号序列,但是 )()( 和 ))) 不是好的括号序列。
有一个字符串 S。最初, S 是一个空字符串。
流程 Q 按给出的顺序进行查询。每次查询后,判断是否 S 是一个很好的括号序列。
有两种类型的查询:
1 c: 一个字符 给出了 c 。 c 是(or)。追加 c 到年底 S.2: 删除最后一个字符 S。可以保证 S 此时不是空字符串。 第一种类型的查询中的
约束
- 1 \leq Q \leq 8 \times 10^5
- c 是
当给出第二类型的查询时,
(or). - 保证 S 不为空。
- Q 是一个整数。
输入
输入由标准输入按以下格式给出,其中 \mathrm{query}_i 表示 i-第一个查询。
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询均以以下两种格式之一给出:
1 c
2
输出
输出 Q 行。的 i- 第行应包含 Yes 如果字符串 S 处理后立即 i-第一个查询是一个很好的括号序列,并且 No 否则。
示例输入 1
8 1 ( 2 1 ( 1 ) 2 1 ( 1 ) 1 )
示例输出 1
No Yes No Yes No No No Yes
S 处理后立即 1st 查询是 (,这不是一个好的括号序列。
S 处理后立即 2nd查询是一个空字符串,这是一个很好的括号序列。
S 处理后立即 3rd 查询是 (,这不是一个好的括号序列。
S 处理后立即 4第一个查询是 (),这是一个很好的括号序列。
S 处理后立即 5第一个查询是 (,这不是一个好的括号序列。
S 处理后立即 6第一个查询是 ((,这不是一个好的括号序列。
S 处理后立即 7第一个查询是 ((),这不是一个好的括号序列。
S 处理后立即 8第一个查询是 (()),这是一个很好的括号序列。