#include #include #include using namespace std; /** * 良い棒付き括弧列 * スタックを用いた (|) の逐次消去による判定 */ int main() { // 入出力の高速化 ios::sync_with_stdio(false); cin.tie(nullptr); int Q; if (!(cin >> Q)) return 0; // stack には現在残っている文字を格納 vector st; // raw_history には、(|) による消去を「行わなかった場合」の // クエリ1で追加された実際の文字の履歴を保存(クエリ2の復元用) // もしくは、消去も含めたスタックの状態そのものを履歴に持ちます。 // 最も確実なのは、各クエリ後のスタックの状態を「完全に復元可能」にすることです。 // 各ステップでのスタックの「文字」と「消去されたかどうかのフラグ」を管理します。 // 構造体でスタックの状態を管理 struct State { char c; }; vector current_st; // クエリ2で「1つ前の状態」に戻す必要があるため、 // 各クエリ直後のスタックを完全に保存するか、 // 変更履歴(どの文字を追加したか、消去が発生したか)を記録します。 // ここでは、各クエリ終了時のスタック全体を管理するのではなく、 // 「追加された文字」をそのまま保持し、消去判定は表示上で行うか、 // あるいはスタックの履歴を vector の vector で持つのはメモリを食い過ぎるので、 // 以下のスタック管理が最も効率的です。 vector> history; // メモリ制限に注意 // Q=8*10^5 なので vector は MLE の危険があります。 // --- 決定版アルゴリズム --- // スタックを1つ用意し、クエリ1なら文字を追加して (|) 判定。 // クエリ2なら「直前のクエリ終了時のスタック」に戻す。 // これを実現するために、スタックそのものの履歴ではなく // 「各時点でのスタックのトップポインタ」と「スタック配列」を永続化っぽく管理します。 vector data; // 物理的なスタックの中身 vector top_history; // 各クエリ終了時のスタックの「端」の位置 top_history.push_back(0); data.reserve(Q); for (int q = 0; q < Q; ++q) { int type; cin >> type; if (type == 1) { char c; cin >> c; // 現在のスタックの状態をコピーして新しい文字を追加 // (実際には前回の位置から継続) int current_top = top_history.back(); // data の current_top の位置に新しい文字を書く if (data.size() <= current_top) { data.push_back(c); } else { data[current_top] = c; } current_top++; // 消去判定: (|) が並んだら top を 3 つ戻す if (current_top >= 3 && data[current_top - 3] == '(' && data[current_top - 2] == '|' && data[current_top - 1] == ')') { current_top -= 3; } top_history.push_back(current_top); } else { // クエリ2: 1つ前のクエリの状態を捨てる if (!top_history.empty()) { top_history.pop_back(); } } // 判定: スタックの長さ(top)が 0 なら Yes if (top_history.back() == 0) { cout << "Yes\n"; } else { cout << "No\n"; } } return 0; }