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

Se da o multime de numere cu $N$ elemente. Se cere sa se efectueze $M$ operatii asupra acestei multimi astfel. Operatiile sunt de $3$ tipuri:

Se da o colectie de numere naturale initial vida. Se cere sa se efectueze $N$ operatii asupra acestei multimi astfel. Operatiile sunt de $3$ tipuri:

* Operatia de tipul 1: inserareaza elementul $x$ in multime
* Operatia de tipul 2: stergerea elementului $x$ din multime
* Operatia de tipul 3: care este elementul minim din multime

* Operatia de tipul 1: inserareaza elementul $x$ in colectie
* Operatia de tipul 2: stergere elementul $NRI[x]$, unde $NRI[x]$ este al $X$-lea element intrat in colectie (in ordine cronologica).
* Operatia de tipul 3: care este elementul minim din colectie

Daca se incearca inserarea unui element care este deja in multime atunci aceasta operatie se ignora. De asemenea stergerea unui element care nu exista in multime se ignora.

Se garanteaza ca nu se vor exista $2$ operatii de tipul $2$ care sa stearga acelasi element din colectie.

h2. Date de intrare

Fisierul de intrare $heapuri.in$ va contine pe prima linie numarele $N$ si $M$. Pe a doua linie se vor afla $N$ numere, reprezentand multimea initiala. Pe liniile $3$ .. $M+2$ se vor afla operatiile descrise astfel: un numar $cod$ reprezentand tipul operatiei, iar in caz ca acesta este $1$ sau $2$ se mai da si un numar $x$ avand semnificatia din enunt.

Fisierul de intrare $heapuri.in$ va contine pe prima linie numarul $N$. Pe liniile $2$ .. $N+1$ se va afla un numar $cod$. $Cod$ reprezinta tipul operatiei care urmeaza a fi efectuata. Daca $cod$ este $1$ sau $2$ atunci se va mai citi si numarul $x$ avand semnificatia din enunt.

h2. Date de ieşire

h2. Restricţii

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 100 000$
* Elementele multimii nu vor depasi $1 000 000$
* Se garanteaza ca multimea nu va fi niciodata goala

* $1 ≤ N ≤ 200 000$
* Elementele colectiei nu vor depasi $1 000 000$
* Se garanteaza ca nu se va cere niciodata sa se afle minimul daca colectia este vida

h2. Exemplu
table(example). |_. heapuri.in |_. heapuri.out |

| 4 6
4 9 7 12

| 9
1 4
1 7
1 9

3
1 2

2 4

2 1

3

2 2

2 4

3

| 4

|
4

2
7
|
h3. Explicaţie

La prima operatie de tipul $3$ multimea arata astfel: {4, 9, 7, 12}
La a doua operatie de tipul $3$ multimea arata astfel: {2, 9, 7 12}
la a treia operatie de tipul $3$ multimea arata astfel: {9, 7, 12}

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 bazeaza pe folosirea unui heap, care suporta aceste efectuarea operatiilor de tipul $1$ si $2$ in $O(log N)$ si a operatiilor de tipul $3$ in $O(1)$.

Un heap este un arbore binar echilibrat, cu proprietatea ca fiecare nod, are asociata o cheie, cheie care este mica decat cheile asociate nodurilor din subarborele sau. Evident raspunsul la operatiile de tip $3$ se vor gasi in radacina arborelui.

Un heap este un arbore binar, cu proprietatea ca fiecare nod, are asociata o cheie, cheie care este mica decat cheile asociate nodurilor din subarborele sau. Evident raspunsul la operatiile de tip $3$ se va gasi in radacina arborelui.

O implementare usoara este aceea de a reprezenta heapul ca pe un vector. Astfel radacina se va afla pe pozitia $1$ iar pentru un nod $i$, fii lui se vor afla pe pozitiile $2*i$ respectiv $2*i+1$.
Cand vrem sa inseram un element nou in vector, il adaugam la capatul sirului, si apoi il interschimbam cu parintele sau pana cand se respecta proprietatea de heap.
De asemenea pentru fiecare element vom tine minte pozitia pe care se afla acesta in vector. Astfel ca atunci cand o sa vrem sa stergem un element din heap, il interschibam cu ultimul element din vector si scadem dimensiunea acestuia cu $1$. Totusi acest lucru ne poate strica proprietatea de heap. Astfel avem $2$ cazuri:

* Elementul nostru este mai mic decat parintele sau, caz in care aplicam acelasi algoritm pe care il aplicam si atunci cand vrem sa adaugam un nod in heap, adica il interschibam cu parintele sau pana cand acesta va fi mai mare decat parintele sau.
* Elementul nostru este mai mare decat fii sai, caz in care vom continua sa il interschimbam cu cel mai mic fiu al sau pana cand acesta va fi mai mare decat ambii sai fii.

*Nota* La fiecare operatie trebuie sa avem grija sa actualizam pozitiile elementelor.
 

Puteti citi "aici":http://infoarena.ro/heapuri mai multe detalii.
h3. Probleme suplimentare