この問題は set と呼ばれるデータ構造を用いることで解くことができます。

set はその名の通り、集合を管理するデータ構造であり、要素の追加・削除および「ある要素が含まれるかどうか」の判定を高速に行うことができます。

データ構造内部の実装方法の違いにより、計算量は \(O(\log N)\) や expected \(O(1)\) となります。（ \(N\) は要素数）

よってこの問題を \(O(Q\log Q)\) で解くことができました。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  set<int>s;
  int q;
  cin >> q;
  while(q--){
    int t, x;
    cin >> t >> x;
    if(t == 1){
      s.insert(x);
    }else{
      if(s.contains(x)){
        cout << "Yes" << endl;
      }else{
        cout << "No" << endl;
      }
    }
  }
}

実装例 (Python)

S = set()
Q = int(input())
for _ in range(Q):
  t, x = map(int, input().split())
  if t == 1:
    S.add(x)
  else:
    if x in S:
      print("Yes")
    else:
      print("No")