h2. Indicatii de rezolvare

Problema se poate rezolva brut-force, cu complexitatea O(N*M), pentru fiecare interogare parcurgem tot intervalul si afisam minimul. Aceasta rezolvare obtiUn alt articol interesant este "acesta":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor , care explica si folosirea algoritmului in calcularea LCA-ului (Lowest Common Ancestorne $30$ de puncte. O sursa care foloseste aceasta abordare gasiti "aici".

Problema se poate rezolva brut-force, cu complexitatea O(N*M), pentru fiecare interogare parcurgem tot intervalul si afisam minimul. Aceasta rezolvare obtine $30$ de puncte. O sursa care foloseste aceasta abordare gasiti "aici".

Putem de asemenea rezolva problema folosind un arbore de intervale. ( vezi problema "Arbori de intervale":http://infoarena.ro/problema/arbint ). Aceasta idee are complexitatea $O(NlogN+MlogN)$ si ar trebui sa obtina $60-70$ de puncte. O sursa care foloseste arbori de intervale gasiti "aici":http://infoarena.ro/job_detail/148285?action=view-source.
Pentru a obtine $100$ de puncte, vom folosi o idee mai simpla decat cea cu arbori de intervale si anume vom folosi algoritmul de Range minimum query care are poate fi redus la complexitatea $O(NlogN + M)$.
O descriere mai pe larg a acestui algoritm gasiti "aici":http://infoarena.ro/preoni-2007/runda-2/solutii la problema $Plantatie$.