*Cosmin:* Articolul asta despre baleiere http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep e destul de bine facut, poti sa trimiti lumea sa il citeasca. Chestia cu aria dreptunghiurilor nu e explicata si in articolul lui Mircea despre arbori de intervale? Mai bine ii trimiti acolo direct, decat sa le mai prezinti acelasi lucru inca o data. Si acolo parca complexitatea e O(n log n) in total.

*Stefan:* Articolul de pe Topcoder o sa-l mentionez impreuna cu altele la bibliografie. La complexitatea problemei cu aria dreptunghiurilor ai avut dreptate si este $O(N * log N)$ (am modificat asta in articol). Cat despre articolul cu 'arbori de intervale':arbori-de-intervale (singurul astfel de articol in romana de care stiu este al doamnei Dana Lica, nu al lui Mircea), acolo este prezentata in detaliu aplicatia cu perimetrul reuniunii de dreptunghiuri, iar cea cu aria este trecuta doar la Probleme propuse. In plus, aplicatia pe care o prezint eu nu vrea sa reproduca pe niciuna din ele, ci este o varianta mult mai simplificata pentru a prezenta tehnica de baleiere. In problema pe care o prezint, un query sau un update vizeaza un singur element dintr-o multime, pe cand in problema generala a ariei dreptunghiurilor, update-ul vizeaza un interval de elemente.

*Stefan:* Articolul de pe Topcoder o sa-l mentionez impreuna cu altele la bibliografie. La complexitatea problemei cu aria dreptunghiurilor ai avut dreptate si este $O(N * log N)$ (am modificat asta in articol). Cat despre articolul cu 'arbori de intervale':arbori-de-intervale (singurul astfel de articol in romana de care stiu este al doamnei Dana Lica, nu al lui Mircea), acolo este prezentata in detaliu aplicatia cu perimetrul reuniunii de dreptunghiuri, iar cea cu aria este trecuta doar la Probleme propuse. In plus, aplicatia pe care o prezint eu nu vrea sa reproduca pe niciuna din ele, ci este o varianta mult mai simplificata pentru a prezenta tehnica de baleiere. In problema pe care o prezint, un query sau un update vizeaza un singur element dintr-o multime, pe cand in problema generala a ariei dreptunghiurilor, update-ul vizeaza un interval de elemente.
 
*Stefan:* :) da e al doamenei Lica .... perimetrul nu merge in O(n log n) perimetru e O(n log n + nr de segmente de pe perimetru) nu am citit articolul dar tind sa cred ca e prezentata treaba cu aria.