Fişierul intrare/ieşire:rmq.in, rmq.outSursăad-hoc
AutorArhiva EducationalaAdăugată dedevilkindSavin Tiberiu devilkind
Timp execuţie pe test1.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Range minimum query

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]?"

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 intrebarile.

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 intrebarea i.

Restrictii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 1 000 000
  • Numerele sunt intervalul [1,100 000]

Exemplu

rmq.inrmq.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
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
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.
Sursa care foloseste aceasta abordare o gasiti aici.
Un alt articol interesant este acesta unde este descris atat algoritmul RMQ cat si folosirea lui in determinarea LCA-ului (Lowest Common Ancestor).
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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content