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. Ei trebuie sa retina care este pozitia pe care o indica in sirul dp[], iar iteratorul (1) mai trebuie sa cunoasca si care este panta sa, intrucat informatiile care vin de la segmente (nodurile din lista) sunt de forma "cu cat se schimba panta", doar ca el trebuie sa cunoasca si sa restabileasca o panta in sine. Cum se demonstreaza ca algoritmul este liniar, si cum, mai exact, ne asiguram ca maximizam sau ca minimizam valoarea lui cnt?
