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)$. Mai mentionam si ca sirul $res$ se poate calcula pe $long long$, fara a fi nevoie de calcul modulo $MOD$ pana la afisare.

private

protected