* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 100 000$

* Elementele multimii nu vor depasi $1 000 000 000$

* Elementele multimii nu vor depasi $100 000$

h2. Exemplu

== include(page="template/taskfooter" task_id="heapuri") ==

h3. Indicatii de rezolvare

h3. Indicatii de rezolvare

Problema se poate rezolva brut-force tinand numerele intrun vector, si efectuand pur si simplu fiecare operatie. Aceasta solutie are complexitate $O(1)$ pe o operatie de tipul $1$ si $O(N)$ pe celelalte si nu ar trebui sa ia $~30$ de puncte.
Rezolvarea optima se face folosind un heap, care suporta aceste efectuarea operatiilor de tipul $1$ si $2$ in $O(log N)$ si a operatiilor de tipul $3$ in $O(1)$.
Pentru detalii despre cum se implementeaza un heap si ce este acesta puteti citi "aici":http://infoarena.ro/heapuri.

*catre Paul si buru*: nu va speriati o sa pun in seara asta si testele si sursa, scuze ca am trecut peste deadline. My bad.

h3. Probleme suplimentare
 
* "Djikstra":http://infoarena.ro/problema/dijkstra
 
 

*Paul*:
1. Fii atent la brutul in N^2 care cauta minimul doar atunci cand stergi elementul minim si restul cazurilor le trateaza O(1).
2. Nu uita ca se poate face si in sqrt (tii pentru fiecare bucata de sqrt(N+M) minimul) si adaugi bucati pe parcurs.

*Cosmin*:
De ce e multime si nu colectie de elemente. Nu imi place ca adaugi o restrictie care nu e necesara la heapuri prin faptul ca zici ca elementele apartin unei multimi.
*devil*

Cand am zis multime ma gandeam mai mult la faptul ca intr-o multime nu poate exista acelasi element de 2 ori. Am uitat insa acest lucru pe parcurs si am uitat sa precizez ca daca un element e deja in heap nu mai intra inca o data si de asemenea am uitat sa pun elementele mai mici ca 100000 ca sa se poate verifica usor acest lucru.

@cosmin: Cand am zis multime ma gandeam mai mult la faptul ca intr-o multime nu poate exista acelasi element de 2 ori, si astfel atunci cand sterg un element e clar ce se intampla. Am uitat insa acest lucru pe parcurs si am uitat sa precizez ca daca un element e deja in heap nu mai intra inca o data si de asemenea am uitat sa pun elementele mai mici ca 100000 ca sa se poate verifica usor acest lucru.
@paul
1. o sa bag un test cu 40000 de inserturi si 40000 de operatii de stergere a minimului si restul queryuri.
2. O sa bag o sursa si sa vad cum fac un test mare. O sa bag 100 000 de elemente la inceput si apoi multe inserturi si stergeri, ca queryurile merg in O(1).
3. Ma gandeam sa las articolu ala, dar ok explic
4. Caut acuma