概要

到着した招待客番号を追加し、問い合わせではその番号がすでに追加済みかを判定する問題です。追加と検索を高速に行えるデータ構造を使います。

考察

重要なのは、操作が最大 \(Q=2\times 10^5\) 回あり、問い合わせ（\(T_i=2\)）のたびに「今までに追加されたか」をすぐに答える必要がある点です。

例えば素朴に、到着した番号をリスト（配列）に追加しておき、問い合わせのたびに先頭から探すとします。
この場合、1 回の問い合わせに最悪 \(O(N)\) かかり、問い合わせが多いと全体で最悪 \(O(Q^2)\) になってしまい、\(2\times 10^5\) では間に合いません（TLE の原因）。

そこで、「追加」と「含まれているか確認」を平均的に高速（ほぼ定数時間）で行える 集合（set） を使うのが適切です。
また \(X_i\) は最大 \(10^9\) と大きいですが、値の範囲が大きくても set ならそのまま扱えます（座標圧縮などは不要）。

アルゴリズム

ゲストリストを集合 \(S\) として管理します。

• 操作 \(T_i=1\)（追加）:
  • \(S\) に \(X_i\) を追加する（\(S.add(X_i)\)）
  • 問題文より「その時点で未登録」が保証されているので重複は気にしなくてよい
• 操作 \(T_i=2\)（問い合わせ）:
  • \(X_i \in S\) を判定し、含まれていれば Yes、なければ No を出力する

例： - 追加: 10 → \(S=\{10\}\) - 問い合わせ: 10 → 含まれるので Yes - 問い合わせ: 7 → 含まれないので No

これを \(Q\) 回順に処理するだけです。

計算量

• 時間計算量: 平均 \(O(Q)\)（各操作の set の add / in が平均 \(O(1)\)）
• 空間計算量: \(O(N)\)（追加された要素数 \(N\) に比例、最大で \(O(Q)\)）

実装のポイント

• Python の set を使うと、追加 s.add(x) と存在判定 x in s が簡潔に書けます。

• 出力は問い合わせの回数だけ発生するので、都度 print するより out に溜めて最後にまとめて出すと高速です。

• 入力も \(2\times 10^5\) 行あるため、sys.stdin.buffer.read() を使った高速入力が安定します。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    Q = int(next(it))
    s = set()
    out = []
    for _ in range(Q):
        t = int(next(it))
        x = int(next(it))
        if t == 1:
            s.add(x)
        else:
            out.append("Yes" if x in s else "No")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。