h3. 'Sir':problema/sir

bq. Se dă un şir de numere întregi de lungime $N$. Se cere să se găsească secvenţa de lungime maximă cuprinsă între $X$ şi $Y$ astfel încât $MAX - MIN ≤ Z$, unde $MAX$ este maximul dintre toate numerele întregi din secvenţă iar $MIN$ minimul dintre acestea.
Restricţii: $3 ≤ N ≤ 100 000$, $1 ≤ X ≤ Y ≤ N$, $0 ≤ Z ≤ 30 000$.

(dequeuri pure)
...

h3. Soluţie
 
Voi prezenta mai jos o rafinare a soluţiei în trei paşi.
 
Prima rezolvare se găseşte uşor, deoarece nu facem decât să urmărim textul: pentru fiecare poziţie $i$ fixată ({$i$} ia valorile $1$, $2$, .., $N$ succesiv) vom determina pentru aceasta secvenţa cerută, adică vom plimba un $j$ între poziţiile $i - Y$ şi $i - X$. Pentru un interval $(j, i]$ vom determina $MAX$ şi $MIN$ în $log{~2~}N$ cu un arbore de intervale, iar daca diferenţa dintre acestea nu depăşeşte $Z$ vom compara cu soluţia finală. Complexitatea finală va fi $(O(N * (Y - X) * log{~2~}Y)$.
 
p=. !deque-si-aplicatii?sir.png 60%!
 
Să presupunem că pentru poziţia curentă $i$, l-am găsit pe $j$ cuprins între $i - Y$ şi $i - X$ care îndeplineşte optimul. Ce proprietăţi are $j$?
 
* $i - Y ≤ j ≤ i - X$;
* dacă îl decrementăm pe $j$, atunci ori $j < i - Y$ ori $MAX - MIN > Z$;
* dacă îl incrementăm pe $i$ la $i + 1$, atunci se poate întâmpla ca $i - X < j$; cum $MAX$ nu poate decât să crească, iar $MIN$ decât să scadă, se mai poate de asemenea întâmpla ca $MAX - MIN > Z$.
 
Datorită proprietăţilor de mai sus, când trecem de la $i$ la $i + 1$, valoarea lui $j$ nu poate decât să crească cât timp $MAX - MIN > Z$ şi $j$ nu a depăşit poziţia $i - X$. Pentru determinarea lui $MAX$, respectiv lui $MIN$ se poate folosi un arbore de intervale. Complexitatea finală va fi $O(N * log{~2~}(Y))$.
 
Cu cei doi indici $i$ şi $j$ vom accesa fiecare element din cele $N$ de cel mult $2$ ori, o dată cu $i$ şi o dată cu $j$. Destul de eficient. Să vedem cum putem îmbunătăţi complexitatea $O(log{~2~}Y)$ pentru determinarea maximului şi minimului. În episodul următor...

h3. 'Trans':problema/trans (ONI 2004)

h3. 'Bcrc':problema/bcrc (Stelele Informaticii 2006)

(deque la programare dinamica)
...