Acum, trebuie sa vedem cum putem raspunde eficient la intrebarea: Cate drumuri contin un interval cautat de organizatori. Vom retine intervalele ca puncte in plan (atat drumurile cat si intrebarile), coordonata x va fi capatul din stanga, iar coordonata y capatul din dreapta. Pentru ca un interval sa fie cuprins de altul, trebuie ca primul punct sa fie in stanga si deasupra celul de-al doilea. Vom sorta crescator toate cele M + T puncte dupa coordonata x si in caz de egalitate descrescator dupa coordonata y. Acum, pt fiecare punct (interval) cautat, raspunsul va fi numarul de puncte cu aflate inaintea lui in vector care au coordonata y mai mare decat a lui.

Vom proceda ca la subsir descrescator maximal. Vom tine un aib (Arbore indexat binar). La pasul i, vom vedea daca punctul curent este din cele M, caz in care vom updata pe pozitia respectiva in aib numarul de cartite care trec pe acel interval, sau in caz ca este din cele T vom vedea in aib cate elemente sunt mai mari ca el.

Vom proceda ca la subsir descrescator maximal. Vom tine un aib (Arbore indexat binar). La pasul i, vom vedea daca punctul curent este din cele M, caz in care vom updata pe pozitia corespunzatoare coordonatei y in aib numarul de cartite care trec pe acel interval, sau in caz ca este din cele T vom vedea cu ajutorul aib-ului cate elemente sunt mai mari ca el.

Solutia are complexitate o((M + T) (log (M + T) + log N)) ca timp si o(N) ca memorie.