Pagini recente » Istoria paginii runda/rar5 | Diferente pentru olimpici intre reviziile 109 si 108 | Monitorul de evaluare | Istoria paginii runda/nr9 | Diferente pentru verkhoyansk/solutie_romana intre reviziile 4 si 3
Nu exista diferente intre titluri.
Diferente intre continut:
h1. Solutia problemei 'Verkhoyansk':problema/verkhoyansk
h1. Solutia problemei 'Verkhoyansk':https://infoarena.ro/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.
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))$.
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
Complexitatea finala a solutiei este de $O((N + Q) * log(N))$.
Diferente intre securitate:
Topicul de forum nu a fost schimbat.
