2093 - Actualizare Element, Stergere Minim

Enunt

Se dă un șir de numere asupra căruia se pot face două tipuri de operații: actualizare a unui element (schimbarea valorii sale) și determinarea, urmată de ștergerea, elementului minim. Dacă valoarea minimă apare de mai multe ori în șir, se elimină prima sa apariție. Se consideră că elementele aflate în dreapta celui eliminat se deplasează o poziție la stânga (acoperă golul lăsat).

Cerinţa

Afișați, după fiecare operație de ștergere, valoarea eliminată.

Date de intrare

Prima linie a fisierului aesm.in conține un număr N, ce reprezintă lungimea șirului dat. Linia a doua, conține, separate prin câte un spațiu, elementele șirului. Pe linia a treia e află un număr M ce reprezintă numărul de operații ce se efectuează asupra șirului. Pe fiecare din următoarele M linii se găsește descrierea unei operații, astfel: fie se găsește pe linie doar numărul 1, fie se găsește numărul 2, urmat de un număr p și de un număr x, separate prin câte un spațiu. Dacă operația este de tip 1, se va determina valoarea minimă din șir și apoi se va șterge prima sa apariție. Dacă operația este de tip 2, elementul aflat în șir pe poziția p va primi valoarea x. Se garantează că la apariția fiecărei astfel de operații șirul conține cel puțin p numere.

Date de ieșire

Fișierul aesm.out conține valorile minime din momentul apariției operațiilor de tip 1, câte una pe linie, în ordinea apariției în fișierul de intrare.

Restricţii şi precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 100.000
• elementele șirului dat sunt indexate de la 1
• elementele șirului dat precum și valoriile x sunt pozitive ≤ 2.000.000.000
• se garantează că numărul de operații de tip 1 este ≤ N

Exemplu

aesm.in

7
1 6 3 9 3 7 2
5
1
2 4 2
1
2 5 8
1

aesm.out

1
2
3

Explicatie

Minimul din șir este 1, aflat pe poziția 1, acesta se afișează și se șterge. Șirul rămâne 6 3 9 3 7 2. După prima operație de tip 2, șirul devine: 6 3 9 2 7 2. Se obține minimul 2 și se șterge acesta, șirul devenind 6 3 9 7 2. A doua operație de tip 2 transformă acum șirul în 6 3 9 7 8. Ultima dată se tipărește și se șterge 3.

Rezolvare

import heapq

def remove_min(nums, heap):
    min_val = nums[heap[0]]
    nums[heap[0]] = None
    heapq.heapify(heap)
    return min_val

def main():
    with open("aesm.in", "r") as fin, open("aesm.out", "w") as fout:
        N = int(fin.readline())
        nums = list(map(int, fin.readline().split()))
        heap = [(num, idx) for idx, num in enumerate(nums) if num is not None]
        heapq.heapify(heap)
        
        M = int(fin.readline())
        for _ in range(M):
            op = fin.readline().split()
            if op[0] == '1':
                min_val = remove_min(nums, heap)
                fout.write(f"{min_val}\n")
            else:
                p, x = map(int, op[1:])
                nums[p - 1] = x
                heapq.heapify(heap)

if __name__ == "__main__":
    main()