Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | rmq.in, rmq.out | Sursă | ad-hoc |
| Autor | Arhiva Educationala | Adăugată de |  Savin Tiberiu •devilkind |
| Timp execuţie pe test | 0.65 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Range minimum query
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]?"
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.
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.
Restrictii
- 1 ≤ N ≤ 100 000
- 1 ≤ M ≤ 1 000 000
Exemplu
| rmq.in | rmq.out |
|---|---|
| 5 4 1 5 6 4 3 2 4 1 2 3 5 1 4 | 4 1 3 1 |
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
Putem de asemenea rezolva problema folosind un arbore de intervale. ( vezi problema Arbori de intervale ). 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.
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 la problema Plantatie.
Un alt articol interesant este acesta 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.
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
