Problema

[•gozzy]

Imi poate acorda si mie cineva o indicatie amcar la cum se rezolva problema asta?


Fie N un număr natural şi un şir de 2N numere naturale X1, X2, …, X2N.

Cerinţa
Trebuie să răspundeţi la un număr de Q întrebări de forma : Date k şi p, care este elementul maxim dintre elementele Xk, Xk+1, …, Xp din şir?

Date de intrare:
Pe prima linie a fişierului maxim.in se află N, pe următoarea linie 2N numere separate prin câte un spaţiu reprezentând elementele şirului. Pe linia a treia se află Q, numărul de întrebări, iar pe următoarele Q linii sunt câte două numere k şi p separate printr-un spaţiu reprezentând capetele secvenţei din care trebuie să aflaţi maximul.

Date de ieşire
Fişierul maxim.out conţine exact Q linii. Pe fiecare linie se află un singur număr S, reprezentând răspunsul la fiecare întrebare din fişierul de intrare.

Restricţii şi precizări
•   2  N  13
•   Xi este un număr între 1 şi 30.000, pentru orice i,  1  i  2N
•   1  k  p  2N
•   1  Q  100.000

Exemplu:
maxim.in
2
4  6  7  1
3
1  4
1  2
2  4   maxim.out
7
6
7   Explicaţie:
Dintre elementele de la poziţia 1 la 4, maximul este 7.
Dintre elementele de la poziţia 1 la 2, maximul este 6.
Dintre elementele de la poziţia 2 la 4, maximul este 7.

[•Cosmin]

Sper ca nu e de la ceva concurs de acuma, eu am gasit-o aici http://lsp.vs.edu.ro/pracsiu/Centrul%20de%20excelenta/subiecte%20OLI/OLI%202006%20Subiecte%209-12.htm

Cauta range minimum query pe google, poti de asemenea citi de RMQ in articolul lui Daniel Pasaila de aici: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor . Pe scurt folosesti matricea a[j] = max (X ... X[i + 2^j - 1]) (i de la 1 la 2^n, j de la 0 la n) pentru a raspunde in O(1) la un query.

[•wefgef]

Concursul era din 2006 , scrie sus la inceput.

[•pauldb]

Merge mai usor cu o preprocesare in O(N^2) sau O(N^3)  si apoi O(1) pe query. Calculezi direct A[i,j] = maximul pe intervalul i,j si raspunzi la query-uri.

[•wefgef]

Sunt 2^N numere, nu 2*N.

[•Florian]

Si daca, de exemplu pt fiecare pereche [i,j] din datele de intrare, numerele din intervalul determinat de ele si-ar modifica valoarea..intr-un mod random, sa zicem. Tot asa cu precalculare in N^3 se face? 

[•wefgef]

Se face cu arbori de intervale.

[•Cosmin]

@wefgef se mai refolosesc probleme, nu ziceam ca concursul din 2006 ar fi unul curent