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))$