#include #include using namespace std; const int MAXQ = 800005; // st[i] : 簡約化スタックの i 番目の位置に最後に書き込まれた文字 char st[MAXQ]; // ptr_history[L] : 文字列 S の長さが L の時の、スタックのポインタ (次に書き込む位置) int ptr_history[MAXQ]; // char_history[L] : 文字列 S の L 文字目を追加した結果、スタックに書き込まれた「場所」 // (クエリ2で戻った時に、スタックのその位置の文字を復元するために使用) int pos_history[MAXQ]; char val_history[MAXQ]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int Q; cin >> Q; int current_S_len = 0; int st_ptr = 0; ptr_history[0] = 0; for (int i = 0; i < Q; ++i) { int type; cin >> type; if (type == 1) { char c; cin >> c; current_S_len++; // 現在のスタックの先端に文字を書き込む st[st_ptr] = c; // 後で復元できるように、スタックのどの位置に何を書いたか記録 pos_history[current_S_len] = st_ptr; val_history[current_S_len] = c; st_ptr++; // (|) 判定 if (st_ptr >= 3 && st[st_ptr-3] == '(' && st[st_ptr-2] == '|' && st[st_ptr-1] == ')') { st_ptr -= 3; } ptr_history[current_S_len] = st_ptr; } else { // クエリ2: Sの長さを減らす current_S_len--; // スタックのポインタを戻す st_ptr = ptr_history[current_S_len]; // 【重要】スタックの中身を、Sの長さが current_S_len だった時の状態に復元する // 直前のクエリ1で書き換えられた可能性があるため if (current_S_len > 0) { st[pos_history[current_S_len]] = val_history[current_S_len]; } } if (st_ptr == 0) cout << "Yes\n"; else cout << "No\n"; } return 0; }