* $bst[i][c] = Min{ Min(bst[j][0], bst[j][1]) - sum[j][c] } + sum[i][c] + T$, unde $i - K ≤ j ≤ i - 1$.
Notez în continuare, pentru uşurinţă în scriere, $X[j][c] = Min(bst[j][0], bst[j][1]) - sum[j][c]$. Să fixăm doi indici $i{~1~}$ şi $i{~2~}$, astfel încât $i - K ≤ $i{~1~}$ < $i{~2~}$ ≤ i - 1$. Dacă $X[i{~1~}][c] > X[i{~2~}][c]$ atunci, întotdeauna poziţia $i{~2~}$ va fi preferată poziţiei $i{~1~}$. Când cele două nu se vor mai afla în intervalul $[i - K, i - 1]$, poziţia eliminată va fi poziţia $i{~1~}$. Dacă $X[i{~1~}][c] < X[i{~2~}][c]$, atunci nu putem decide care poziţie este mai în viitor, aşa că le vom păstra pe ambele. Rezultă mai departe că în intervalul $[i - K, i - 1]$ vom avea o serie de indecşi candidaţi la minim $i - K ≤ i{~1~} < i{~2~} < .. < i{~n~} ≤ i - 1$ astfel încât $X[i{~1~}][c] < X[i{~2~}][c] < .. < X[i{~n~}][c]$. Când vom avansa la poziţia $i + 1$ vom elimina din $i{~1~}$, $i{~2~}$, .. cât timp aceştia vor fi mai mici strict decât $i - K$. De asemenea, găsim $bst[i + 1][c]$ ca fiind $X[i{~1~}][c] + sum[i + 1][c] + T$. Urmează să îl introducem şi pe $X[i + 1][c]$, el fiind egal cu $Min(bst[i + 1][0], bst[i + 1][1]) - sum[i + 1][c]$, în şirul de indecşi de mai sus. Acest lucru se va face în felul următor: se vor elimina din $i{~n~}$, $i{~n-1~}$, ... atâta timp cât $X[$i{~n~}$] > X[i + 1]$, $X[$i{~n-1~}$] > X[i + 1]$, ... adică atâta timp cât poziţia $i + 1$ este preferată.
Notez în continuare, pentru uşurinţă în scriere, $X[j][c] = Min(bst[j][0], bst[j][1]) - sum[j][c]$. Să fixăm doi indici $i{~1~}$ şi $i{~2~}$, astfel încât $i - K ≤ $i{~1~}$ < $i{~2~}$ ≤ i - 1$. Dacă $X[i{~1~}][c] > X[i{~2~}][c]$ atunci, întotdeauna poziţia $i{~2~}$ va fi preferată poziţiei $i{~1~}$. Când cele două nu se vor mai afla în intervalul $[i - K, i - 1]$, poziţia eliminată va fi poziţia $i{~1~}$. Dacă $X[i{~1~}][c] < X[i{~2~}][c]$, atunci nu putem decide care poziţie este mai în viitor, aşa că le vom păstra pe ambele. Rezultă mai departe că în intervalul $[i - K, i - 1]$ vom avea o serie de indecşi candidaţi la minim $i - K ≤ i{~1~} < i{~2~} < .. < i{~n~} ≤ i - 1$ astfel încât $X[i{~1~}][c] < X[i{~2~}][c] < .. < X[i{~n~}][c]$. Când trebuie să avansăm la poziţia $i + 1$ vom elimina din $i{~1~}$, $i{~2~}$, .. cât timp aceştia vor fi mai mici sau egali decât $i - K$. De asemenea, găsim $bst[i][c]$ ca fiind $X[i{~1~}][c] + sum[i][c] + T$. Urmează să îl introducem şi pe $X[i][c]$, el fiind egal cu $Min(bst[i][0], bst[i][1]) - sum[i][c]$, în şirul de indecşi de mai sus. Acest lucru se va face în felul următor: se vor elimina din $i{~n~}$, $i{~n-1~}$, ... atâta timp cât $X[$i{~n~}$][c] > X[i][c]$, $X[$i{~n-1~}$][c] > X[i][c]$, ... adică atâta timp cât poziţia $i$ este preferată lui $i{~n~}$, $i{~n-1~}$...
După cum am arătat şi la problema precedentă, acest şir de indecşi $i{~1~}$, $i{~2~}$, .., $i{~n~}$ are proprietatea că este un şir continuu de numere care admite inserări prin dreapta (tail) şi ştergeri prin stânga (head). Care poate fi, deci, un deque. Cum fiecare index dintre $1$, $2$, .., $N$ va trece o singură dată prin deque şi va fi şters cel mult o dată, complexitatea soluţiei în acest caz va fi $O(Q * N)$.
