Problem A
Binärt sökträdsoperationer

Din uppgift är att implementera en datastruktur som hanterar två operationer: insättning av ett tal och kontroll om ett tal existerar i strukturen

Mer i detalj ska datastrukturen stödja följande två operationer:

1. insert(k) - Lägg till ett positivt heltal $k$ i datastrukturen. Om talet redan finns i datastrukturen, ska det inte läggas till flera gånger.

2. exist(k) - Kontrollera om ett positivt heltal $k$ redan finns i datastrukturen. Skriv ut 1 om det finns, annars 0.

Efter alla operationer ska programmet skriva ut alla tal som finns i strukturen i sorterad ordning.

Dessa operationer ska kunna utföras effektivt.

Indata

Första raden av indatan består av ett heltal $N$ $(1 \leq N \leq 5 \cdot 10^5)$, antalet operationer som ska utföras av sort $1$ eller $2$.

De följande $N$ raderna beskriver en operation var. Det finns två typer av operationer:

• ”1 k”, som representerar operationen insert(k) $(0 \leq k \leq 10^9)$, som beskrivet ovan.

• ”2 k”, som representerar operationen exist(k) $(0 \leq k \leq 10^9)$, som beskrivet ovan.

Utdata

För varje operationer som börjar på ”2” (exist(k)-operationen), ska programmet skriva ut 1 om talet $k$ existerar i datastrukturen, och 0 annars. Svara på varje fråga i samma ordning som de förekommer i indatan, en per rad.

Efter alla operationer ska programmet även skriva ut alla tal som finns i datastrukturen på en ny rad, sorterade i ökande ordning, separerade med mellanslag.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av Exempelfall 1

Efter första operationen insert(5) innehåller datastrukturen talet 5.

Efter insert(10) innehåller datastrukturen talen 5 och 10.

exist(5) returnerar 1 eftersom talet 5 finns i datastrukturen.

exist(7) returnerar 0 eftersom talet 7 inte finns i datastrukturen.

insert(7) lägger till talet 7.

exist(7) returnerar 1 eftersom talet 7 nu finns i datastrukturen.

6
1 5
1 10
2 5
2 7
1 7
2 7

1
0
1
5 7 10

5
2 10
1 10
2 10
1 10
2 10

0
1
1
10