infoarena

Salut. As vrea sa stiu daca problema urmatoare are alta solutie mai optima:

Fie un arbore. Initial toate nodurile au aceeasi valoare, mostenite de la radacina. Se fac urmatoarele operatii pe arbore:
1. nodul x ia valoarea y, caz in care toate nodurile din subarborele cu radacina in x care il mostenesc iau valoarea y.
2. seteaza nodul x sa mosteneasca parintele (caz in care se poate modifica valoarea nodului x => operatia 1)
3. aflarea valorii nodului x

Prima solutie care imi vine in minte este ca pentru operatia 1 si 2 sa parcurg subarborele si sa setez valorile, iar aflarea valorii unui nod sa fie in O(1). Exista o solutie mai eficienta, atat din pt de vedere al timpului cat si al memoriei ?
Multumesc anticipat.

E destul de ciudat enuntul, sper ca am inteles bine problema. Presupun ca daca A il mosteneste pe B si B pe C atunci si A pe C.

O solutie mai buna ar fi sa imparti cele M query-uri in bucati de sqrt(M). Pentru fiecare bucata, calculezi vectorul S[i] = stramosul cu nivelul minim pe care il mosteneste (cel mai de sus). Apoi, operatiile se fac astfel:

2. O(1), pur si simplu marchezi.
1. O(1), marchezi la nodul x ca la query-ul cu indexul i i s-a atribuit valoarea y.
3. Ai lista L de noduri ale caror valoare s-a schimbat (maxim sqrt(M)). Mergi din x pana in stramosul cu nivelul minim (posibil diferit de S[i]) in maxim sqrt(M) pasi si de fiecare data cand treci pe langa un nod din L vezi cu ce valoare a contribuit la x.

Iese complexitatea O(N*sqrt(M) + M*sqrt(M)).

Ai inteles bine enuntul. Insa problema e ca acele queryuri sunt intercalate. Sunt N operatii care pot fi de tipul 1,2 sau 3, lucru pe care am uitat sa il specific  ](*,)

Solutia mea tine cont de asta.

Atunci nu am inteles eu solutia ta. Cum pot sa impart queryurile in bucati de sqrt de M daca nu le cunosc numarul? Tot ce stiu este ca sunt N operatii care trebuie executate in ordine.

Ok, posibil sa ma fi exprimat gresit. Prin query ma refeream la operatii. N operatii (la tine) = M query-uri (la mine).

Ideea pare buna insa nu stiu daca se mai poate implementa daca problema este interactiva (numarul de operatii nu este cunoscut de la inceput)  :-k

Ba merge. Faci in O(sqrt(N)) unde N e marimea initiala a arborelui. In rest ramane aceeasi solutie. Defapt e cel mai bine sa faci asa si n in bucati de O(sqrt(M)) pentru ca asa complexitatea devine O(M sqrt(N)) in loc de O(M sqrt(M)). In rest e super buna solutia lui @George Marcus.

Ok. Multumesc mult de solutie :)