Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-09-28 20:11:06.
Revizia anterioară   Revizia următoare  

Dat fiind ca ne trebuie operatii de genul:

  • shifteaza graficul
  • gaseste (1) minimul din dp (echivalent, locul in care panta este 0)
  • insereaza in dreptul minimului un segment
  • gaseste (2) pozitia indicelui 0 in dp
  • modifica pantele in dreptul lui 0
  • scade panta ultimului segment (ca din lambda+1 (asa cum a schimbat-o operatia 1) sa redevina lambda)

Cel mai elegant fel de a le realiza este sa tinem o lista dublu inlantuita cu segmentele, care nu vor retine coordonatele lor precise, pentru ca sunt foarte dinamice, ci doar cu cat se schimba panta in dreptul lor si care este lungimea lor. De asemenea, vom retine daca au fost create intr-o operatie de tipul 2 ori ba, intrucat, asta inseamna ca toate segmentele din dreapta lor au trecut prin aceasta operatie iar cnt-ul lor creste cu 1 (sub forma unui smen al lui Mars).

Avem nevoie de iteratorii (1) si (2) pentru a realiza operatiile in timp constant amortizat. Cum se demonstreaza ca algoritmul este liniar, si cum, mai exact, ne asiguram ca maximizam sau ca minimizam valoarea lui cnt?