h1. Solutie pentru problema 'Verkhoyansk':https://infoarena.ro/problema/verkhoyansk

h1. Solutia problemei 'Verkhoyansk':problema/verkhoyansk

Definitie: Rezultatul calculat pentru fiecare interval $[l, r]$ se numeste mex-ul acelui interval. Aceasta definitie va fi folosita frecvent in solutiile urmatoare.

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

Vom cauta binar raspunsul, folosind arborele de intervale. Fiecare nod al sau ne va spune daca toate valorile din intervalul ce defineste nodul pot fi vazute in intervalul din query. Conditia este doar ca $aint[nod]$ sa fie mai mare sau egal cu capatul stanga al query-ului. Folosind conditia aceasta, vom cauta raspunsul binar in timp ce ne vom deplasa prin arborele de intervale in $O(log(N))$.

Complexitatea finala a solutiei este de $O((N + Q) * log(N))$.

Complexitatea finala a solutiei este de $O((N + Q) * log(N))$.
 
h3. Nota si Multumiri
 
Multumim lui ==user(user="Matteoalexandru" type="tiny")== pentru traducerea in limba romana a solutiei!
 
Pentru varianta in engleza a editorialului, vizitati 'pagina sa':verkhoyansk/solutie

public

protected