== include(page="template/taskheader" task_id="rmq") ==

Se da un vector cu $N$ elemente. Scrieti un program care raspunde la $M$ intrebari de genu "Care este elementul minim din intervalul [$x$,{$y$}]?"

Se da un vector cu $N$ elemente. Scrieti un program care raspunde la $M$ intrebari de tipul "Care este elementul minim din intervalul [$x$,{$y$}]?"
 

h2. Date de intrare

Pe prima linie a fisierului $rmq.in$ sunt date numerele $N$ si $M$. Urmatoarele $N$ linii vor contine cate un numar reprezentand elementele vectorului. Urmatoarele $M$ linii vor contine cate $2$ numere reprezentand valorile $x$ si $y$ care definesc interogarile.

Pe prima linie a fisierului $rmq.in$ sunt date numerele $N$ si $M$. Urmatoarele $N$ linii vor contine cate un numar reprezentand elementele vectorului. Urmatoarele $M$ linii vor contine cate $2$ numere reprezentand valorile $x$ si $y$ care definesc intrebarile.

h2. Date de iesire

In fisierul de iesire $rmq.out$ vor fi $M$ linii, fiecare continand cate un numar, pe linia $i$ aflandu-se raspunsul pentru interogatia $i$.

In fisierul de iesire $rmq.out$ vor fi $M$ linii, fiecare continand cate un numar, pe linia $i$ aflandu-se raspunsul pentru intrebarea $i$.

h2. Restrictii
* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 1 000 000$

* Numerele sunt intervalul [{$1,100 000$}]

h2. Exemplu

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 obtine $30$ de puncte. O sursa care foloseste aceasta abordare gasiti "aici":http://infoarena.ro/job_detail/148408?action=view-source
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$.

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":job_detail/148408?action=view-source
O alta abordare poate o fi solutie care raspunde la un query in {$O(sqrt(n))$}. Vom folosi un vector {$A$} in care retinem minimul pe bucati de lungime {$sqrt(N)$}. In momentul unui query luam minimul dintre toate bucatile de lungime {$sqrt(N)$} incluse complet in intervalul dat, apoi pur si simplu parcurgem valorile din interval care nu le-am luat in considerare.
Aceasta solutie obtine 40 de puncte. O sursa gasiti "aici":job_detail/151694?action=view-source
Putem de asemenea rezolva problema folosind un arbore de intervale ( vezi problema "Arbori de intervale":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":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 poate fi redus la complexitatea $O(NlogN + M)$.
O descriere mai pe larg a acestui algoritm gasiti "aici":preoni-2007/runda-2/solutii la problema $Plantatie$.
Sursa care foloseste aceasta abordare o gasiti "aici":job_detail/148283?action=view-source.

Un alt articol interesant este "acesta":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor unde este descris atat algoritmul RMQ cat si folosirea lui in determinarea LCA-ului (Lowest Common Ancestor).

Sursa care foloseste aceasta abordare o gasiti "aici":http://infoarena.ro/job_detail/148283?action=view-source.
 
*Cosmin:* Ideea de la RMQ se poate folosi si la alte operatii cum ar fi la operatia de determinare a celui mai mic divizor comun pentru o subsecventa, de exemplu in problema 'euclid':problema/euclid

Ideea de la RMQ se poate folosi si la alte operatii cum ar fi la operatia de determinare a celui mai mare divizor comun pentru o subsecventa, de exemplu in problema 'Euclid':problema/euclid.

== include(page="template/taskfooter" task_id="rmq") ==

2823