h2(#aplicatii). Aplicaţii

Folosiţi deque! Foarte sănătos! :)

În multe aplicaţii unde soluţiile parţiale se reprezintă sub forma unui şir continuu de valori care permite inserarea şi ştergerea doar pe la capete (în general inserări pe la un capăt şi ştergeri pe la celălalt) se poate folosi un deque. Să urmărim în continuare cazuri concrete în care simplitatea unui deque duce la soluţii de multe ori optime şi implementări foarte scurte şi clare.

h3(#problema-1). Problema 1: 'Book Pile':http://acm.sgu.ru/problem.php?contest=0&problem=271 (SGU)

Întrucât operaţiile unui deque se execută în $O(1)$ amortizat, soluţia are complexitatea $O(N + M)$.

h3(#problema-2). Problema 2: 'Sir':problema/sir

h3(#problema-2). Problema 2: 'Şir':problema/sir

bq. Se dă un şir $S$ 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. Secvenţa soluţie va fi cea cu poziţia de început maximă dintre toate secvenţele de lungime maximă.
Restricţii: $3 ≤ N ≤ 100 000$, $1 ≤ X ≤ Y ≤ N$, $0 ≤ Z ≤ 30 000$.

Rezultă din această observaţie că în intervalul $(j, i]$ poziţiile importante vor fi $j < i{~1~} < i{~2~} < .. < i{~k~} <= i$ astfel încât $S[i{~1~}] > S[i{~2~}] > .. > S[i{~k~}]$. Astfel, $MAX$ va fi $S[i{~1~}]$. Când îl vom incrementa pe $i$ la $i + 1$ vom şterge din poziţiile $i{~k~}$, $i{~k-1~}$, ... atâta timp cât $S[i + 1]$ este mai important, adică mai mare decât valorile de pe aceste poziţii, şi vom şterge $i{~1~}$, $i{~2~}$, ... atâta timp cât aceste poziţii sunt mai mici sau egale decât $j'$. Indicele $j'$ este noul optim pentru poziţia $i + 1$. Proprietatea şirului de poziţii $i{~1~}, i{~2~}, .., i{~k~}$ este că se reprezintă ca un şir contiguu de numere care permite inserarea elementelor prin dreapta şi ştergerea prin stânga, adică se adaugă elemente la tail şi se şterg elemente de la head. Îl putem deci reprezenta printr-un deque. Complexitatea $O(1)$ amortizat provine de la faptul că fiecare poziţie dintre cele $N$ nu trece decât o singură dată prin deque şi este şters tot cel mult o singură dată.

În practică, programul poate arăta în felul următor:

În practică, pseudocodul poate arăta în felul următor:

== code(cpp) |
// S şirul de numere iniţial şi N lungimea sa