Solutia corecta la aceasta problema presupune cunoasterea structurii de date 'Arbore de intervale':http://www.infoarena.ro/problema/arbint.

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 erau parantezate corect, este indeajuns o stiva.

Problema se poate rezolva prin mentinerea in fiecarui 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 erau parantezate corect, este indeajuns o stiva.

Cand primim o inserare, descompunem intervalul primit in cele logN noduri corespunzatoare din arborele de intervale, si incarcam in varful stivei din fiecare din aceste noduri 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).