Fişierul intrare/ieşire:	mergeheap.in, mergeheap.out	Sursă	arhiva educationala
Autor	Filipescu Radu, Mititelu Teodor	Adăugată de	Filipescu Radu •Radu_Filipescu
Timp execuţie pe test	0.15 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Heapuri cu reuniune

Fie N mulţimi de elemente. Asupra acestor mulţimi se vor efectua 3 tipuri de operaţii.

• operaţia de tipul 1: se inserează elementul x în mulţimea m.
• operaţia de tipul 2: se afişează elementul maxim din mulţimea m, apoi se elimină din aceasta.
• operaţia de tipul 3: se reunesc mulţimile a şi b ( mulţimea a preia elementele mulţimii b, care rămâne vidă )

Date de intrare

Fişierul de intrare mergeheaps.in va conţine pe prima linie valorile lui N şi Q, care reprezintă numărul de mulţimi pe care se vor face operaţiile, respectiv numărul de operaţii. Pe următoarele Q linii se va afla un număr care reprezintă tipul operaţiei, urmat apoi de o valoare, dacă tipul operaţiei este 2, respectiv de două valori pentru operaţiile 1 şi 3.

Date de ieşire

Fişierul de ieşire mergeheaps.out va contine, pe câte o linie, răspunsul pentru fiecare operaţie de tipul 2 din fişierul de intrare, în ordinea data.

Restricţii

• 1 ≤ N ≤ 100
• 1 ≤ Q ≤ 200000
• Elementele mulţimilor sunt numere naturale, mai mici decât 2 000 000 000.
• Se garantează că nu se va cere operaţia 2 pentru o mulţime vidă.

Exemplu

Explicaţie

Primele 5 operaţii introduc elemente în mulţimi. La a 6-a operaţie trebuie afişat maximul din a doua mulţime, cea care conţine elementele 2 şi 5. Deci vom afişa 5 şi îl vom elimina din mulţimea sa. Apoi trebuie reunite a doua mulţime cu prima, a doua conţinând, dupa reuniune, elementele 2 şi 3. Apoi ni se cere să afişăm elementul maxim din această mulţime. Penultima operaţie este de reuniune dintre mulţimile 3 şi 2, urmată apoi de afişarea şi eliminarea maximului din aceasta.

Indicaţii de rezolvare

O soluţie simplă constă în folosirea unor heapuri binare, care sunt uşor de implementat şi vor efectua operaţiile de adăugare şi de eliminare în complexitate logaritmică. Problema acestora este operaţia de reuniune, care se efectuează în O(N*log ₂ N), dacă introducem element cu element o mulţime în cealaltă, sau în O(N), folosind heapify pentru construirea unui heap.

Pentru a efectua mai rapid operaţia de reuniune, se pot folosi structuri de date precum Binomial Heap sau Pairing Heap, care efectuează operaţiile de tipul 3 în O(log 2 N), respectiv în O(1) amortizat.

Complexităţile operaţiilor pentru aceste structuri de date, precum şi câteva alternative ale acestora.

Cum se trimit solutii?