Soluţia problemei Pensula

Atunci cand arborele este un lant cu radacina intr-unul din capete, fiecare culoare (ignorand pentru o clipa faptul ca o culoare poate fi folosita de mai multe ori) ocupa un interval continuu de noduri. La fiecare operatie, un prefix al sirului de noduri este recolorat. Cu alte cuvinte, cateva intervale de la inceput dispar, altul este scurtat, iar cel nou este adaugat, fiind primul interval de la stanga la dreapta. Daca privim felul in care evolueaza sirul de capete drepata ale acestor intervale, observam ca operatiile sunt acelea suportate de stiva. Atunci cand stergem un interval, gradul de zapaceala al fiecarui nod din intervalul respectiv creste cu aceeasi valoare, xor-ul dintre culoarea intervalului si cea noua. Deoarece vrem sa aflam aceste valori numai la final, putem folosi smenul lui Mars. Aceasta solutie are complexitatea O(N + Q). Mai mentionam si ca sirul res se poate calcula pe long long, fara a fi nevoie de calcul modulo MOD pana la afisare.

Pentru restul punctelor, vom descompune arborele in lanturi. Culorile fiecarui lant in parte se comporta asemanator cu descrierea de mai sus, singura diferenta fiind aceea ca nu numai operatiile care recoloreaza direct un nod apartinand lantului afecteaza intervalele, ci si acelea care modifica orice nod din subarborii acestora. Fiecare operatie aplicata unui anumit nod va afecta exact acele lanturi pe care le intersecteaza drumul de la el la radacina. O descompunere eficienta in acest caz este aceea in care, atunci cand ne punem intrebarea, cu care dintre fiii unui anumit nod sa-i continuam lantul, il alegem pe acela cu cele mai multe noduri. Astfel, numarul de lanturi pe drumul de la un nod la radacina este O(logN), iar complexitatea solutiei de 100 de puncte este O(N + Q logN).

Se merita sa analizam si doua solutii care pot obtine 80 de puncte. Una dintre ele trateaza lanturile ca inainte, doar ca foloseste o alta descompunere in lanturi. In loc sa extindem lantul curent cu nodul al carui subarbore are cele mai multe noduri, il alegem pe acela pentru care inaltimea maxima din subarbore e cat mai mare. Astfel, numarul de lanturi de pe drumul de la un nod la radacina este O(sqrt(N)) iar complexitatea solutiei este O(N + Q sqrt(N)).

Cealalta solutie de 80 de puncte foloseste descompunerea optima, doar ca nu trateaza in timp liniar un lant. In schimb, vom construi un arbore de intervale ale carui noduri sunt exclusiv de tip "lazy", pe care le vom propaga la fiecare atingere a unui nod. In fiecare nod, vom retine trei numere despre intervalul curent: a = prima (cronologic) culoare care nu a fost impinsa in subintervale, b = ultima (cronologic) culoare care nu a fost impinsa in subintervale, si s = suma xor-urilor perechilor de culori consecutive care s-au acumulat intre a si b. Observatia e ca atunci cand propagam o informatie dintr-un nod in altul, stim ca toate culorile impinse au aparut ulterior (cronologic) (mai mult: imediat dupa) culorilor din intervalul mai mic. Prin urmare, atunci cand propagam aceasta informatie intr-un subinterval, adunam interval.s + (subinterval.b ^ interval.a) la subinterval.s si modificam subinterval.b in interval.b. Solutia are complexitatea O(N + Q logN logN).