Acum, pentru fiecare query, o inaltime non-speciala poate fi vizitata doar din exteriorul galetii, in timp ce inaltimile speciale pot fi vizitate si din interiorul sau. Ideea din spatele solutiei este sa pastram un mex partial pentru fiecare interval de inaltimi non-speciale, considerand doar inaltimile de la $(G + 1) * K$ la sfarsitul query-ului.

Ca sa fim mai precisi, $partialMex[x]$ va retine cel mai mic numar intreg cu valoarea mai mare sau egala cu $x$ care nu poate fi intalnita intre inaltimile de la $(B + 1) * K$ la capatul dreapta curent.

Ca sa fim mai precisi, $partialMex[x]$ va retine cel mai mic numar intreg cu valoarea mai mare sau egala cu $x$ care nu poate fi intalnita intre inaltimile de la $(G + 1) * K$ la capatul dreapta curent.

De asemenea, este important sa observam ca este de ajuns sa calculam $partialMex[x]$ doar pentru $x$-urile de la care porneste un interval de inaltimi non-speciale. Pentru exemplul de mai sus, $partialMex[x]$ este important doar pentru $x = 1, 6 sau 24$.

In concluzie, pentru fiecare galeata, in timp ce ne mutam in dreapta si raspundem la query-uri, tinem cont de mex-ul partial al fiecarui interval de inaltimi non-speciale. Astfel, pentru fiecare query vom vedea maxim $2 * K + 1$ valori: inaltimile speciale si cele $K + 1$ intervale, prin care "sarim" in timp constant, datorita mex-ului partial pe care il tinem pentru fiecare dintre ele. De asemenea, mex-ul partial pentru fiecare interval poate sa creasca de un numar de ori egal cu lungimea intervalului, in total de maxim $N$ ori pentru fiecare bucket.

Hai sa analizam complexitatea algoritmului. Pentru fiecare galeata, vizitam $O(N)$ pozitii, deoarece cel mai mare capat dreapta al unui query este $N - 1$. De asemenea, vom creste vectorul $partialMex$ tot de $O(N)$ ori. Pentru fiecare query, vom face $O(K)$ pasi suplimentari pentru a afla raspunsul. In total, complexitatea este $(O * N * N / K + Q * K), care isi atinge minimul cand $K$ este egal cu $N / sqrt(Q)$. Astfel se ajunge la o complexitate de $O(N * sqrt(Q) + Q)$.

Hai sa analizam complexitatea algoritmului. Pentru fiecare galeata, vizitam $O(N)$ pozitii, deoarece cel mai mare capat dreapta al unui query este $N - 1$. De asemenea, vom creste vectorul $partialMex$ tot de $O(N)$ ori. Pentru fiecare query, vom face $O(K)$ pasi suplimentari pentru a afla raspunsul. In total, complexitatea este $(O * N * N / K + Q * K)$, care isi atinge minimul cand $K$ este egal cu $N / sqrt(Q)$. Astfel se ajunge la o complexitate de $O(N * sqrt(Q) + Q)$.

Totusi, solutia necesita sortarea query-urilor dupa capatul lor dreapta pentru fiecare galeata, deci complexitatea finala este de $O(N * sqrt(Q) + Q * log(Q)).

Totusi, solutia necesita sortarea query-urilor dupa capatul lor dreapta pentru fiecare galeata, deci complexitatea finala este de $O(N * sqrt(Q) + Q * log(Q))$.

h2. $O((N + Q) * log(N))$