题解：AT_abc428_c [ABC428C] Brackets Stack Query

Camellia2025 · 2025-10-19 11:55:24 · 题解

首先如果我们将左括号看成一，右括号看成负一，那么当当前前缀和值为零时，便是一个合法的序列。

但是还有一个问题，就是如果有某个位置前缀和为负的话，说明那里一定至少有一个右括号会失配，那么直接记录这个位置就好了。

code

#include <bits/stdc++.h>
using namespace std;

int len, lst, a[800010], sum[800010]; 

int main () {
    int q;
    cin >> q;
    while (q--) {
        int opt;
        char c;
        cin >> opt;
        if (opt == 1) cin >> c, a[++len] = (c == '(' ? 1 : -1), sum[len] = sum[len - 1] + a[len];
        else a[len--] = 0, lst = (len < lst ? 0 : lst);
        if (lst) cout << "No" << endl;
        else {
            if (sum[len] < 0) lst = len, cout << "No" << endl;
            else cout << (sum[len] ? "No" : "Yes") << endl;
        }
    }
    return 0;
}