Imprimă pagina

Titlul: aib
Scris de: Ciocan Andrei din Noiembrie 18, 2010, 17:18:01

Pot folosi AIB-uri querry/update pt minime? (querry pt interval 1-n) Nu prea stiu sa fac update-ul cand inlocuiesc valoarea minima din AIB (mi-a trecut prin minte ceva mult prea naspa ~ log^2 ). :)

Titlul: Răspuns: aib
Scris de: Pripoae Teodor Anton din Noiembrie 19, 2010, 15:32:28

Pe aib poti cauta minimul doar pe intervalul (1, x):

Cod:


void update (int poz, int val) {
    for (; poz <= N; poz += lsb(poz))
        aib[poz] = min(aib[poz], val);
}

Si query-ul :

Cod:

int query (int poz) {
    int ret = inf;
    for (; poz; poz -= lsb(poz))
        ret = min(ret, aib[poz);
    return ret;
}

Titlul: Răspuns: aib
Scris de: Ciocan Andrei din Noiembrie 19, 2010, 17:09:59

Ok...numai ca in pb-ma apare si cazul in care trebuie sa sterg un element din AIB (il initializez cu infinit ). Eu daca trebuie sa elimin chiar elementul minim din aib (si sa inlocuiesc cu valoarea infinit), ce valoare pun in AIB[poz] ? Cum fac update-ul mai exact? Nu credk merge tot aib[poz]=min(aib[poz],val) pt ca valoarea aib[poz] e minimul vechi care trebuie sters, iar val este de fapt infinit... :| Sper ca ma intelegi :D

Mie mi se pare destul de dubios. Credk finalizez cu AI pana la urma :)

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Ciocan Andrei din Noiembrie 18, 2010, 17:18:01