h2. Pentru 10 puncte
Vom mentine sirul $next[i]$ si vom face operatiile in ordinea data. La update, putem parcurge tot sirul $next[]$ si daca $next[i] == x$, il schimbam in $next[x]$. La query, putem merge din $a$ in $next[a]$ pana cand am mai ajuns intr-un nod vizitat la acest query si vom retine care este timpul $timpA$ la care vom deschide fiecare videclip vizitat. Apoi din $b$ vom face o parcurgere asemanatoare. La final, se considera videoclipurile vizitate atat din $a$, cat si din $b$, si se ia acela pentru care $max(timpA, timpB)$ este cat mai mic. Daca nu exista nod vizitat de ambii, afisam infinit.
Vom mentine sirul $next[i]$ si vom face operatiile in ordinea data. La update, putem parcurge tot sirul $next[]$ si daca $next[i] == x$, il schimbam in $next[x]$. La query, putem merge din $a$ in $next[a]$ pana cand am mai ajuns intr-un nod vizitat la acest query si vom retine care este timpul $timpA$ la care vom deschide fiecare videoclip vizitat. Apoi din $b$ vom face o parcurgere asemanatoare. La final, se considera videoclipurile vizitate atat din $a$, cat si din $b$, si se ia acela pentru care $max(timpA, timpB)$ este cat mai mic. Daca nu exista nod vizitat de ambii, afisam infinit.
h2. Pentru 100 de puncte
Mai intai remarcam ca structura grafului format din muchiile orientate (i, next[i]) este o multime de componente conexe, iar fiecare componenta conexa este un ciclu simplu de care sunt agatati mai multi arbori. Ca observatie, ciclcul poate fi format si dintr-un singur nod, in caz ca next[x] == x.
La un query ce ar trebui sa vedem este in primul rand daca nodurile se afla in aceeasi componenta conexa. In caz ca nu, afisam infinit. Altfel, ar trebui sa stim daca fac parte din acelasi arbore cu radacina pe ciclul componentei lor, sau se afla in arbori diferiti. Daca se afla in acelasi arbore, afisam maximul intre distanta de la $a$ la $lca(a, b)$ si distanta de la $b$ la $lca(a, b)$ (prin $lca(a, b)$ am notat lowest common ancestor). Daca se afla pe arbori diferiti, notam cu $A$ radacina arborelui lui $a$ si cu $B$ radacina arborelui lui $b$. Atunci raspunsul este $minim(maxim(dist(a, A) + dist(A, B), dist(b, B)), maxim(dist(b, B) + dist(B, A), dist(a, A)))$.
La un query ce ar trebui sa vedem este in primul rand daca nodurile se afla in aceeasi componenta conexa. In caz ca nu, afisam infinit. Altfel, ar trebui sa stim daca fac parte din acelasi arbore cu radacina pe ciclul componentei lor, sau se afla in arbori diferiti. Daca se afla in acelasi arbore, afisam maximul intre distanta de la $a$ la $lca(a, b)$ si distanta de la $b$ la $lca(a, b)$ (prin $lca$ am notat 'lowest common ancestor':problema/lca). Daca se afla pe arbori diferiti, notam cu $A$ radacina arborelui lui $a$ si cu $B$ radacina arborelui lui $b$. Atunci raspunsul este $minim(maxim(dist(a, A) + dist(A, B), dist(b, B)), maxim(dist(b, B) + dist(B, A), dist(a, A)))$.
La un update e ca si cand am modifica $durata[x] = 0$, mai putin pentru clipele in care se da un query in care $a$ sau $b$ este egal cu $x$, caz in care reconsideram $durata[x]$ la valoarea ei normala. Vom face distinctie intre cazul in care nodul apartine unui ciclu sau strict unui arbore.
* Afla distanta de la un nod la un stramos al sau intr-un arbore
* Afla distanta de la un nod la altul intr-un ciclu
Aceste operatii ne duc cu gandul la liniarizarea plus-minus a arborilor si la mentinerea unui arbore indexat binar atat peste aceste liniarizari, cat si peste a ciclilor. Putem mentine un singur aib pentru toti arborii, daca le concatenam liniarizarile. Asemanator putem proceda cu ciclii. Mentionam ca mai trebuie sa obtinem si $lca$ in timp logaritmic.
Aceste operatii ne duc cu gandul la liniarizarea plus-minus a arborilor si la mentinerea unui arbore indexat binar atat peste aceste liniarizari, cat si peste ciclii. Putem mentine un singur aib pentru toti arborii, daca le concatenam liniarizarile. Asemanator putem proceda cu ciclii. Mentionam ca mai trebuie sa obtinem si $lca$ in timp logaritmic.
Complexitate finala: timp $O((N + Q) * logN)$, memorie $O(N * logN)$ (pentru precalcularea necesara pentru $lca$).
