#include #include #include using namespace std; /** * Bài toán: No.3503 Brackets Stack Query 2 * Độ phức tạp: O(Q) - Mỗi truy vấn xử lý trong O(1) */ int main() { // Tối ưu tốc độ nhập xuất ios_base::sync_with_stdio(false); cin.tie(NULL); int Q; cin >> Q; // Duy trì stack ký tự và trạng thái dp // dp[i] = true nếu chuỗi S độ dài i là "dãy ngoặc gậy tốt" vector s_stack; vector dp(Q + 1, false); // Chuỗi rỗng luôn là dãy tốt dp[0] = true; int current_len = 0; for (int i = 0; i < Q; ++i) { int type; cin >> type; if (type == 1) { char c; cin >> c; s_stack.push_back(c); current_len++; // Kiểm tra xem tại độ dài current_len, chuỗi có "tốt" không // Điều kiện: 3 ký tự cuối cùng tạo thành (|) và phần trước đó cũng phải tốt if (current_len >= 3 && s_stack[current_len - 1] == ')' && s_stack[current_len - 2] == '|' && s_stack[current_len - 3] == '(') { dp[current_len] = dp[current_len - 3]; } else { dp[current_len] = false; } } else { // Truy vấn loại 2: Xóa ký tự cuối if (!s_stack.empty()) { s_stack.pop_back(); current_len--; } } // Xuất kết quả sau mỗi truy vấn if (dp[current_len]) { cout << "Yes\n"; } else { cout << "No\n"; } } return 0; }