$S$ に含まれる( の数と ) の数は等しい。
任意の $1 \leq k \leq |S|$ に対して、 $\begin{equation*} (S の先頭から k 文字目までの\texttt{'('}の個数) \geq (S の先頭から k 文字目までの\texttt{')'}の個数) \end{equation*}$

これを、条件 (☆) と呼ぶことにする。

2 つ目の条件は、例えば)(())(のような文字列が良い括弧列でないことを考えれば分かりやすいだろう。

条件 (☆) は前述の $T, A$ を用いて表すと、

$A_{|S|} = 0$
任意の $1 \leq k \leq |S|$ に対して、 $A_k \geq 0$

となるから、各クエリの直後に条件 (☆) を満たすかを判定すればよい。

...普通はこれで良いのだが、今回は $Q$ が最大で $8 \times 10^5$ と大きいため、各クエリの直後に $A$ の全要素を調べるのでは、判定のための計算量が $O(Q)$ となってしまい、間に合わない。

そこで、以下で定義される $A$ の累積 min 数列 $B$ を導入する。

B_i = \min_{1 \leq j \leq i} A_j \quad (B_0 = 0)

すると、条件 (☆) はさらに以下のように言い換えられる。

$A_{|S|} = 0$
$B_{|S|} \geq 0$

こうすることで、各クエリの直後に $A_{|S|}$ と $B_{|S|}$ の 2 つを調べるだけでよくなり、この部分の計算量が $O(1)$ になる。

クエリの処理

一方、各クエリは次のように処理できる。ここで、数列は全てstackで実装する。

1 c : $c$ に対応する値を $t$ とし、 $A$ の末尾に $A_{|S|} + t$ を追加する。その後、 $B$ の末尾に $\min(B_{|S|}, A_{|S|})$ を追加する。
2 : $A$ と $B$ の末尾をそれぞれ削除する。

実装例も参考のこと。

これらの処理は全て計算量 $O(1)$ で行えるため、全体の計算量は $O(Q)$ となる。

これは、本問の制約下で十分に高速である。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.// ======================================== //
5. 
6.int main()
7.{
8.    int Q;
9.    cin >> Q;
10. 
11.    stack<int> A, B;
12.    A.push(0);
13.    B.push(0);
14. 
15.    while (Q--)
16.    {
17.        int t;
18.        cin >> t;
19. 
20.        if (t == 1)
21.        {
22.            char c;
23.            cin >> c;
24. 
25.            A.push(A.top() + (c == '(' ? 1 : -1));
26.            B.push(min(B.top(), A.top()));
27.        }
28.        else if (t == 2)
29.        {
30.            A.pop();
31.            B.pop();
32.        }
33. 
34.        if (A.top() == 0 && B.top() >= 0)
35.            cout << "Yes" << endl;
36.        else
37.            cout << "No" << endl;
38.    }
39. 
40.    return 0;
41.}