#include #include using namespace std; // Cấu trúc một nút trong "Persistent Stack" struct Node { char c; int parent; int depth; }; // Mảng lưu các trạng thái stack // Q <= 8e5, mỗi Node tốn khoảng 12 bytes -> ~10MB, rất an toàn. Node nodes[800005]; int state_at_step[800005]; // Trạng thái stack sau truy vấn thứ i của chuỗi S int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int Q; cin >> Q; // Trạng thái ban đầu (stack rỗng) nodes[0] = {' ', -1, 0}; state_at_step[0] = 0; int s_len = 0; // Độ dài thực tế của chuỗi S int node_count = 0; // Tổng số nút đã tạo ra for (int i = 0; i < Q; ++i) { int type; cin >> type; if (type == 1) { char c; cin >> c; int prev_state = state_at_step[s_len]; s_len++; // Thử kiểm tra xem có tạo thành bộ (|) không bool simplified = false; if (c == ')') { int p1 = prev_state; // Nút chứa '|' ? if (p1 != 0 && nodes[p1].c == '|') { int p2 = nodes[p1].parent; // Nút chứa '(' ? if (p2 != 0 && nodes[p2].c == '(') { // Nếu khớp (|), trạng thái mới chính là trạng thái trước khi có '(' state_at_step[s_len] = nodes[p2].parent; simplified = true; } } } if (!simplified) { // Nếu không rút gọn được, tạo một nút mới trong cây stack node_count++; nodes[node_count] = {c, prev_state, nodes[prev_state].depth + 1}; state_at_step[s_len] = node_count; } } else { // Loại 2: Xóa ký tự cuối của S, chỉ cần quay về trạng thái trước if (s_len > 0) s_len--; } // Chuỗi S là dãy tốt nếu trạng thái stack hiện tại là rỗng (nút 0) if (state_at_step[s_len] == 0) { cout << "Yes\n"; } else { cout << "No\n"; } } return 0; }