Pravdepodobne ste už používali set (množina) v C++ alebo v Pythone. Je to dátová štruktúra,
s ktorou je možné robiť dve základné operácie:
V obyčajnej množine navyše platí, že každý prvok sa v nej nachádza najviac raz. Ak by sme chceli nejaký prvok vložiť dvakrát, druhý pokus nebude mať žiaden efekt (prvok sa v množine bude stále nachádzať len raz).
V tejto úlohe však nepoužívajte set zo štandardných knižníc. Namiesto toho si naprogramujte
vlastnú dátovú štruktúru.
Pre túto úlohu stačí obyčajný binárny strom bez vyvažovania, no nikto vám nebráni použiť tieto vstupy na otestovnie vášho treapu, skip-listu, red-black stromu ...
Budete dostávať dva typy požiadaviek:
Na každú požiadavku prvého typu treba odpovedať YES, ak sa prvok nachádza v množine (bol
už vložený), inak NO.
Na prvom riadku je číslo $n$ ($1 \leq n \leq 10^5$) — počet požiadaviek.
Na ďalších $n$ riadkoch sú popisy jednotlivých požiadaviek. Na $i$-tom riadku sú dve čísla $t_i$ a $x_i$ popisujúce $i$-tu požiadavku.
Ak $t_i = 1$, tak sa jedná o požiadavku prvého typu. Na túto požiadavku treba odpovedať, či sa číslo $x_i$ nachádza v množine.
Ak $t_i = 2$, tak sa jedná o požiadavku druhého typu a číslo $x_i$ treba vložiť do množiny.
Platí $t_i \in {1, 2}$ a $1 \leq x_i \leq 10^9$.
Pre každú požiadavku prvého typu vypíšte jeden riadok a na ňom reťazec \texttt{YES}, ak sa dané číslo nachádza v množine, inak reťazec \texttt{NO}.
8
2 5
2 4
2 8
1 2
1 3
1 4
2 3
1 3
NO
NO
YES
YES
V druhej požiadavke prvého typu sa ešte číslo $3$ v množine nenachádzalo, no pri spracúvaní poslednej požiadavky už áno.