C - Brackets Stack Query Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

文字列 T が次の条件を満たすとき、T を良い括弧列と呼びます。

  • 次の操作を 0 回以上繰り返すことで T を空文字列にすることができる。

    • T に(連続な)部分文字列として含まれる () を選び、これを取り除く。

例えば () や (()()), および空文字列は良い括弧列ですが、)()( や ))) は良い括弧列ではありません。

文字列 S があります。S ははじめ空文字列です。
以下で説明されるクエリを与えられる順に Q 個処理してください。そして、各クエリの直後に S が良い括弧列であるかを判定してください。
クエリは次の 2 種類です。

  • 1 c: 文字 c が与えられる。c は ( または ) である。c を S の末尾に追加する。
  • 2: S の末尾の文字を削除する。この時、S は空文字列でないことが保証される。

制約

  • 1 \leq Q \leq 8 \times 10^5
  • 1 種類目のクエリの c は ( または )
  • 2 種類目のクエリを与えられた時点で S は空でないことが保証される
  • Q は整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。

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

各クエリは以下の 2 種類のいずれかの形式で与えられる。

1 c

2

出力

Q 行出力せよ。i 行目には、i 番目のクエリを処理した直後の文字列 S が良い括弧列である場合は Yes を、そうでない場合は No を出力せよ。

入力例 1

8
1 (
2
1 (
1 )
2
1 (
1 )
1 )

出力例 1

No
Yes
No
Yes
No
No
No
Yes

1 番目のクエリを処理した直後の S は ( で、これは良い括弧列ではありません。
2 番目のクエリを処理した直後の S は空文字列で、これは良い括弧列です。
3 番目のクエリを処理した直後の S は ( で、これは良い括弧列ではありません。
4 番目のクエリを処理した直後の S は () で、これは良い括弧列です。
5 番目のクエリを処理した直後の S は ( で、これは良い括弧列ではありません。
6 番目のクエリを処理した直後の S は (( で、これは良い括弧列ではありません。
7 番目のクエリを処理した直後の S は (() で、これは良い括弧列ではありません。
8 番目のクエリを処理した直後の S は (()) で、これは良い括弧列です。

Score : 300 points

Problem Statement

A string T is called a good bracket sequence if and only if it satisfies the following condition:

  • T can be made into an empty string by repeating the following operation zero or more times:

    • Choose () contained in T as a (contiguous) substring and remove it.

For example, (), (()()), and the empty string are good bracket sequences, but )()( and ))) are not good bracket sequences.

There is a string S. Initially, S is an empty string.
Process Q queries in the order they are given. After each query, determine whether S is a good bracket sequence.
There are two types of queries:

  • 1 c: A character c is given. c is either ( or ). Append c to the end of S.
  • 2: Remove the last character of S. It is guaranteed that S is not an empty string at this time.

Constraints

  • 1 \leq Q \leq 8 \times 10^5
  • c in queries of the first type is ( or ).
  • It is guaranteed that S is not empty when a query of the second type is given.
  • Q is an integer.

Input

The input is given from Standard Input in the following format, where \mathrm{query}_i denotes the i-th query.

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

Each query is given in one of the following two formats:

1 c

2

Output

Output Q lines. The i-th line should contain Yes if the string S immediately after processing the i-th query is a good bracket sequence, and No otherwise.

Sample Input 1

8
1 (
2
1 (
1 )
2
1 (
1 )
1 )

Sample Output 1

No
Yes
No
Yes
No
No
No
Yes

S immediately after processing the 1st query is (, which is not a good bracket sequence.
S immediately after processing the 2nd query is an empty string, which is a good bracket sequence.
S immediately after processing the 3rd query is (, which is not a good bracket sequence.
S immediately after processing the 4th query is (), which is a good bracket sequence.
S immediately after processing the 5th query is (, which is not a good bracket sequence.
S immediately after processing the 6th query is ((, which is not a good bracket sequence.
S immediately after processing the 7th query is ((), which is not a good bracket sequence.
S immediately after processing the 8th query is (()), which is a good bracket sequence.