Solutia problemei Verkhoyansk
Definitie: Rezultatul calculat pentru fiecare interval [l, r] se numeste mex-ul acelui interval. Aceasta definitie va fi folosita frecvent in solutiile urmatoare.
O(N * Q)
Brute-Force. Procesam query-urile online, asa cum ne sunt date in input. Vom folosi un vector de bool vizitat si vom parcurge de la capetele stanga la dreapta ale query-ului si vom marca inaltimile ca vizitate. Apoi vom lua raspunsul ans de la 1 si il vom mari cat timp vizitat[ans] este adevarat. Apoi vom reseta valorile din vectorul vizitat la 0, pentru a fi folosite corect la urmatoarele query-uri.
O(N * sqrt(Q) + Q * log(Q))
Vom imparti vectorul inaltimilor in galeti de marime K (valoarea sa va fi stabilita ulterior). Astfel, vor fi N / K galeti. Observatie: K nu trebuie neaparat sa divida N. Ultima galeata poate avea marime mai mica.
Vom raspunde offline la query-urile pentru aflarea mex-ului. Pentru fiecare galeata, consideram ca toate query-urile au capatul stanga in galeata selectata si vom raspunde la toate. Dupa ce toate query-urile si-au gasit raspunsul, vom putea sa le afisam in ordine.
Sa presupunem ca vrem sa calculam raspunsurile pnetru toate query-urile care au capatul stanga intr-o galeata G. Capetele lor dreapta pot fi oricat de mari, dar capetele lor stanga vor fi toate in acelasi interval [G * K, (G + 1) * K - 1]. Vom considera ca toate inaltimile aflate in acest interval sunt speciale. Toate celelalte inaltimi sunt non-speciale.
Se poate observa ca sunt maxim K inaltimi speciale si maxim K + 1 intervale de inaltimi non-speciale. De exemplu, daca inaltimile speciale sunt intre 5 si 23, N = 100, intervalele de inaltimi non-speciale sunt [1 - 4], [6 - 22] si [24 - 100].
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 (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.
Pentru a pastra acese valori in mod corect, vom sorta query-urile (pentru galeata curenta) dupa capatul lor dreapta. Primele query-uri vor avea capetele dreapta in interiorul galetii, deci putem itera prin inaltimile din interval si sa calculam mex-ul lor intr-o maniera brute-force, deoarece vom face maxim K pasi.
Urmatoarele query-uri vor incepe sa depaseasca limita dreapta, asa ca vom marca noile inaltimi ca vizitate. Vom marca doar inaltimile aflate in exteriorul galetii in vectorul de bool vizitat. De asemenea, vom marca toate inaltimile, indiferent daca sunt speciale sau nu.
Pentru fiecare query, vom calcula raspunsul in felul urmator: Vom incepe cu ans = 1 si vom incerca sa-l marim. La fiecare pas, ans va reprezenta o inaltime care este speciala sau nu. Daca este speciala, marim ans daca inaltimea poate fi regasita in galeata, la dreapta capatului stang, sau este marcat ca si vizitat; altfel ne oprim si returnam ans. Daca nu este special, inseamna ca apartine unui interval anume, asa ca vom verifica in vectorul partialMex cat putem sa marim ans. Daca mex-ul partial spune ca tot intervalul a fost deja vizitat, atunci vom cu cresterea lui ans de la 1 + capatul-dreapta-al-intervalului. Daca ne-am oprit in mijlocul unui interval, inseamna ca mex-ul partial este raspunsul la query. In acest mod, folosim toate inaltimile din query.
Implementarea oficiala calculeaza partialMex[x] in mod "lenes" (nu atunci cand marcam inaltimile ca vizitate, ci atunci cand avem nevoie de valoarea sa cand raspundem la un query). Deci, atunci cand avem ans egal cu prima inaltime non-speciala a intervalului curent, vom incerca sa marim partialMex[ans] cat timp ramanem intr-un interval de inaltimi non-speciale si cat timp valoarea a fost deja vizitata in afara galetii (marcata in vectorul vizitat). Atunci vom spune ca ans = partialMex[ans] si tot asa...
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).
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)).
O((N + Q) * log(N))
Vom procesa query-urile offline, in ordine crescatoare a capetelor din dreapta. In timp ce ne mutam prin vectorul de inaltimi si raspundem la query-uri, va trebui sa retinem pentru fiecare intaltime ultima sa aparitie in vector pana la momentul in care ne aflam. Sa presupunem ca stim aceste valori. Apoi, pentru fiecare query, va trebui sa gasim cea mai mare valoare val, astfel incat toate valorile de la 1 la val - 1 au pozitia mai mare sau egala cu capatul stanga al query-ului.
Putem folosi un arbore de intervale pentru a calcula aceste valori. Mai precis, pastram vectorul posdr[x] cu semnficatia: care este cea mai din dreapta pozitie a carei inaltime este x pe care am intalnit-o pana acum (pana la capatul dreapta al query-ului)? posdr[x] = -1 daca nu am intalnit pana acum inaltimea x. Arborele de intervale va retine minimul acestor valori.
Cand schimbam capatul dreapta al query-ului curent, putem pur si simplu sa notificam vectorul posdr cu noua valoare intampinata. Fiecare schimbare in acest vector inseamna O(log(N)) schimbari in arborele de intervale. Deci stim cum sa modificam arborele de intervale, dar cum gasim mex-ul cu ajutorul lui?
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)).
Nota si Multumiri
Multumim lui 
Pentru varianta in engleza a editorialului, vizitati pagina sa
