h3. Ordonare: $O(N)$, fara reducere

Solutia oficiala (care nu face reducerea de care am vorbit mai devreme) are complexitatea $O(N logN)$. Cu toate acestea, particularitile problemei fac in asa fel incat sa pastram operatiile dar sa schimbam structura de date si sa obtinem complexitate liniara!
 
Am pregatit un 'hint':... care va deslusi care este structura aceasta de date. Incercati sa va prindeti cum se poate folosi. Am scris si 'un scurt articol':... care descrie noua solutie.
 
Puteti gasi 'aici':job_detail/2652506?action=view-source o implementare usoara a ideii. Problema e ca are comportament patrati pe anumite teste. Sursa se poate modifica usor, asa cum puteti vedea in aceasta 'poza':... la un text-compare cu implementarea corecta, pe care o puteti gasi 'aici':job_detail/2653564?action=view-source.
 

Solutia oficiala (care nu face reducerea de care am vorbit mai devreme), deoarece foloseste ...['click daca vrei sa aflii numele structurii de date':afla-cu-ce-se-codeaza-slope-trick], are complexitatea $O(N logN)$. Cu toate acestea, particularitile problemei fac in asa fel incat sa pastram operatiile dar sa schimbam structura de date si sa obtinem complexitate liniara! 'click daca vrei sa aflii ce structura de date e asa de smechera':wow-ce-poate-fi-asa-de-smecher
Puteti citi 'un scurt articol':ordonare-prea-usor care extinde editorialul cu aceasta metoda. 'Aici':job_detail/2653564?action=view-source puteti vedea o posibila implementare. O alta 'sursa':job_detail/2652506?action=view-source arata varianta simplificata a solutiei (recomand citirea acesteia mai intai), dar care are comportament patratic pe unele teste. Pentru convenienta, pun un 'link':my-text-compare-ordonare cu o poza la un text-compare intre cele 2 submisii, pentru a fi si mai clar.