題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟠 ABC428C Brackets Stack Query

Problem Statement

題目簡述

給定一個初始為空的字串 $S$ ，依序處理 $Q$ 次操作：

操作 1：在 $S$ 末尾追加 ( 或 )
操作 2：刪除 $S$ 的最後一個字元

每次操作後，判斷 $S$ 是否為合法括號序列（good bracket sequence）。

Constraints

約束條件

$1 \le Q \le 8 \times 10^5$
操作 1 中 $c$ 為 ( 或 )
執行操作 2 時，保證 $S$ 非空

思路：括號平衡值 + 前綴最小值

如何在

\mathcal{O}(1)

時間內判斷當前字串是否為合法括號序列？

合法括號序列的充要條件

定義字串中每個字元的權值：( 為 $+1$ ，) 為 $-1$ 。令 $\text{cnt}_i$ 表示前 $i$ 個字元的權值前綴和（即到位置 $i$ 的括號平衡值）。

關鍵觀察

一個字串是合法括號序列，若且唯若同時滿足：

$\text{cnt}_n = 0$ （左右括號數量相等）
$\min(\text{cnt}_1, \text{cnt}_2, \ldots, \text{cnt}_n) \ge 0$ （任何前綴中 ) 都不多於 (）

當條件 1 成立時，條件 2 等價於 $\min(\text{cnt}_1, \text{cnt}_2, \ldots, \text{cnt}_n) = 0$ （因為 $\text{cnt}_0 = 0$ 且 $\text{cnt}_n = 0$ ，最小值不可能為正）。

支援撤銷的堆疊結構

操作 2（刪除末尾字元）本質是撤銷上一次操作 1。這啟發我們用堆疊來維護狀態：

st1：儲存每個時刻的前綴和 $\text{cnt}_i$ ，棧頂即為當前平衡值
st2：儲存到每個時刻為止的前綴最小值 $\min(\text{cnt}_1, \ldots, \text{cnt}_i)$ ，棧頂即為全域最小值

操作 1（追加字元 $c$ ）：

計算新的前綴和： $\text{cnt}_{i+1} = \text{cnt}_i + (\text{c} = \texttt{'('} \;?\; +1 : -1)$ ，壓入 st1
更新前綴最小值： $\min_{i+1} = \min(\text{cnt}_{i+1},\; \min_i)$ ，壓入 st2

操作 2（刪除末尾）：

兩個堆疊同時彈出棧頂，回退到前一個狀態

判斷：

檢查 st1[-1] == 0 and st2[-1] == 0 即可

正確性說明

堆疊的 LIFO 特性天然對應「撤銷最後一次操作」的語義。每次操作後，棧頂始終反映當前字串 $S$ 的平衡值和前綴最小值，因此判斷只需 $\mathcal{O}(1)$ 。

複雜度分析

時間複雜度： $\mathcal{O}(Q)$ — 每次操作僅需 $\mathcal{O}(1)$ 的堆疊操作
空間複雜度： $\mathcal{O}(Q)$ — 堆疊最多儲存 $Q$ 個元素

Code

def solve():
    Q = int(input())

    # 維護 cnt_i 以及 min(cnt_1, cnt_2, ..., cnt_i)
    st1, st2 = [0], [0]
    for _ in range(Q):
        op, *args = input().split()
        if op == "1":
            c = args[0]
            st1.append(st1[-1] + (1 if c == "(" else -1))
            st2.append(min(st1[-1], st2[-1]))
        else:
            st1.pop()
            st2.pop()
        # 只有當 cnt_i == 0 且 min(cnt_1, cnt_2, ..., cnt_i) == 0 時，才能恰好匹配
        print("Yes" if st1[-1] == 0 and st2[-1] == 0 else "No")


if __name__ == "__main__":
    solve()