Problema se poate rezolva mentinand in fiecare nod al unui arbore de intervale o structura de date auxiliara care sa poata sa raspunda rapid la inserari, stergeri si query-uri de minim (de exemplu, heap). Insa, cum operatiile de inserare si stergere la problema aceasta sunt parantezate corect, este indeajuns o stiva.

Cand primim o inserare, descompunem intervalul primit in cele $logN$ noduri corespunzatoare din arborele de intervale, iar in varful stivei din fieacre din aceste noduri incarcam min(inaltimea noii nave, varful precedent al stivei). La stergere, luam intervalul asociat ultimei inserari (care il vom memora probabil tot cu ajutorul unei stive) si, din nou, il descompunem in cele $logN$ noduri asociate, pe stivele carora apelam pop()(stergem varful).

Cand primim o inserare, descompunem intervalul primit in cele $logN$ noduri corespunzatoare din arborele de intervale, iar in varful stivei din fieacre din aceste noduri incarcam min(inaltimea noii nave, varful precedent al stivei). La stergere, luam intervalul asociat ultimei inserari (care il vom memora probabil tot cu ajutorul unei stive) si, din nou, il descompunem in cele $logN$ noduri asociate, pe stivele carora apelam $pop$()(stergem varful).

De notat este ca problema nu necesita lazy-update, intrucat query-urile sunt punctiforme (nu sunt pe interval). Un query va parcurge pe arborele de intervale un drum de la radacina la o frunza. Daca in fiecare dintre nodurile de pe drum, ne uitam la ce se afla in varful stivei, raspunsul pentru query va fi minimul dintre aceste valori.

==include(page="onis-2015/solutii-runda-1/livada")==

Sa consideram o rezolvare prin programare dinamica si o dinamica cu urmatoarea semnificatie:
* dp[i][j] = valoarea maxima a unei livezi care contine celula (i,j) si poate contine celule de pe linii ≤ i.
 
O rezolvare in <tex>O(N*M^3^)</tex> este destul de la indemana. Parcurgem liniile de la 1 la i. Presupunand dinamica calculata pentru liniile &l; i

==include(page="onis-2015/solutii-runda-1/meciul")==