Nu aveti permisiuni pentru a descarca fisierul grader_test3.in
Diferente pentru descriere/nave/bunicu-hint4 intre reviziile #2 si #3
Nu exista diferente intre titluri.
Diferente intre continut:
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
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.
