← 返回题目列表

AtCoder · abc428_c

F. 括号堆栈查询

中文机器翻译题面 查看原题

分数: 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第一个查询是 (()),这是一个很好的括号序列。