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$?

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$?