Zadanie týchto troch úloh je rovnaké, ako zadania úloh pre binárny vyhľadávací strom z kurzu Dátové štruktúry 1. V týchto úlohách sú však inak štruktúrované vstupy, a preto ti BST neprejde.
V úlohách Lepší simple set 1 a Lepší simple set 2 ste sa hrali s množinami, kde sa každý prvok mohol nachádzať najviac raz.
V tejto úlohe budete naopak pracovať s tzv. multiset — množina, v ktorej sa každý prvok môže nachádzať ľubovoľný počet krát.
Táto množina bude podporovať tri operácie:
Pokiaľ dostaneme požiadavku na odstraňovanie a daný prvok sa v množine nenachádza, táto operácia nemá žiaden efekt.
Podobne, ako v úlohách Lepší simple set 1 a Lepší simple set 2, nepoužívajte
multiset zo štandardných knižníc, ale naprogramujte si vlastnú dátovú štruktúru.
Budete dostávať tri typy požiadaviek:
Na každú požiadavku prvého typu treba vypísať jedno číslo — koľkokrát sa dané číslo nachádza v množine.
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ť vypísaním jedného čísla: počet výskytov $x_i$ 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.
Ak $t_i = 3$, tak sa jedná o požiadavku tretieho typu a z množiny treba zmazať jeden výskyt čísla $x_i$.
Platí $t_i \in {1, 2, 3}$ a $1 \leq x_i \leq 10^9$.
Pre každú požiadavku prvého typu vypíšte jeden riadok a na ňom jedno číslo — počet výskytov daného čísla v množine.
9
1 4
2 2
1 2
2 2
1 2
3 2
1 2
2 4
1 4
0
1
2
1
1
Najprv sme číslo $2$ vložili do množiny dvakrát, potom sme jeden výskyt zmazali.