h1. 'Soluţia':incalzire2020/solutii/pensula problemei 'Pensula':problema/pensula

h1(#pensula). 'Soluţia':incalzire2020/solutii/pensula problemei 'Pensula':problema/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)$.

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)$.

private

protected