Hint 4

nave-bunicu-hint4

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 log^2^ 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)$).

Scrie aici despre nave-bunicu-hint4