Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-10-04 15:05:01.
Revizia anterioară   Revizia următoare  

Am fi tentati sa folosim un arbore de intervale ca sa calculam eficient aceste costuri.

Operatiile de care avem nevoie sunt:
* Aduna/Scade 1 pe intervalul [X, Y]
* Numara cate numere sunt pozitive/negative pe un interval

Din pacate (din cunostiintele mele), aceasta structura nu se poate implementa eficient, asa ca a trebuit sa recurg la altceva.

Observatie:

Fie 2 operatii op1 = update(X1, Y1, val) si op2 = update(X2, Y2, val). Atunci daca [X2, Y2] se intersecteaza cu [X1, Y1] => X2 ≤ X1 ≤ Y1 ≤ Y2.

Pe parcurs intervalele pe care le interogam/updatam se obtin practic dintr-o fuziune de intervale mai vechi. Astfel putem sa ne gandim la o structura un pic diferita:
* Adauga/scade 1 la toate elementele din structura
* Numara cate numere sunt pozitive/negative in structura
* Uneste doua instante de aceasta structura.

Acestea pot fi implementate cu un deque (dar NU cu std::deque deoarece ocupa prea multa memorie si cand e gol) sau cu un map (platind un log N in plus la complexitate). Primele 2 operatii se pot executa in O(1) mentinand frecventa fiecarui numar si un shift aplicat tuturor indicilor. Cand vrem sa unim 2 astfel de structuri mutam elementele din structura mia mica in cea mai mare.

Tema: Demonstrati ca complexitatea finala este O(N) pentru aceasta structura.

Complexitatea finala este: O(N) (de la structura) + O(K log N) (de la heap-ul care mentine mereu drumul de cost minim)

Solutia se generalizeaza si la capacitati variabil de mari folosind fie un map - cu complexitate finala O(N log2 N), fie cu un treap - cu complexitate finala O(N log N) (a uni 2 treapuri de marime N si M (M ≥ N) are complexitate O(N log (M / N)).