h2. Subtaskul 6, $100$ puncte
Sa grupam valorile dupa ce cicluri apartin in cele doua permutari, si sa luam o multime de astfel de numere, $S$ (care apartin aceluiasi ciclu in ambele permutari). Fie $Cycle(T)$ un sir astfel incat scrierea fiecarui ciclu din $T$ ca elemente consecutive din acesta este o subsecventa din $Cycle(A)$. Exemplu: pentru $T = [5, 3, 2, 1, 4], Cycle(T)$ poate fi egal si cu $[5, 4, 1, 3, 2]$, si cu $[2, 3, 1, 5, 4]$. Nu conteaza valoarea efectiva atata timp cat se pastreaza proprietatea mentinuta anterior. Fie o valoare $r$ pentru care vrem sa calculam raspunsul. Pentru fiecare valoare $a$, din $S$, sa consideram pozitia acesteia din $Cycle(B)$, ca $I{~a~}$. Sa punem un marker intr-un vector paralel cu $Cycle(B)$ pe pozitia $I{~a~} - d{~A~}(r, a)$ pentru fiecare $a$. Este clar ca numarul de markere de pe pozitia $I{~r~}$ include un mare numar de elemente din solutia noastra. Singura problema vine de la valorile $u$ care au $I{~u~} < I{~r~}, $I{~u~} + D_B{~u~} - d{~A~}(r, u} = I{~r~}$ ^({$3$})^ (In termeni mai familiari, $u$ ar ajunge la $r$ "prin spatele ciclului din B"). Pentru a repara aceasta, sugeram lucrarea pe un vector similar lui $Cycle(B)$, dar care ar repara aceasta problema. Introducem notiunea sirului $Cycle^2^(B)$, a carui definitie este similara, doar ca scrierea fiecarui ciclu (ca elemente consecutive din parcugerea acestora) este scrisa de doua ori (in aceeasi ordine de fiecare data). Exemplu: pentru $T = [5, 3, 2, 1, 4], Cycle(T)$ poate fi egal si cu $[5, 4, 1, 5, 4, 1, 3, 2, 3, 2]$, si cu $[2, 3, 2, 3, 1, 5, 4, 1, 5, 4]$. Din nou, nu conteaza cu care varianta lucram atata timp cat se pastreaza aceste propietati. Continuam cu notiunea markerelor, doar ca pentru fiecare valoare $a$ din $S$, punem un marker cu $d{~A~}(r, a)$ pozitii inapoi relativ de fiecare aparitie a acesteia din $Cycle^2^(B)$. Acum, este clar ca existenta problematica a unui $u$ mentionat anterior este reparata de aparitia acestuia la cele $D_B{~u~}$ unitati mai in fata in sir (intr-atat ca ^({$3$})^ se respecta). Acum, structura data (a markerelor) ne poate raspunde corect la queryuri. Singura problema este ca aceasta este (in momentul de fata) descrisa cat sa poata sa raspunda corect^({$4$})^ doar la queryuri privind pe $r$. Trebuie sa reparam asta. Sa presupunem ca avem la indemana un $r'$ care respecta ca pentru orice alt $a$ in $S$, $a != r$, avem ca $d{~A~}(r,a) ≥ d{~A~}(r, r')$. Atunci, pozitiile markerelor se vor schimba (daca am vrem sa adaptam structura noastra de date la a raspunde la queryuri pentru $r'$) asemenea:
Să grupăm valorile după ce cicluri aparţîn în cele două permutări, şi să luăm o mulţime de astfel de numere, $S$ (care aparţîn aceluiaşi ciclu în ambele permutări). Fie $Cycle(T)$ un şir astfel încât scrierea fiecărui ciclu din $T$ că elemente consecutive din acesta este o subsecventă din $Cycle(A)$. Exemplu: pentru $T = [5, 3, 2, 1, 4], Cycle(T)$ poate fi egal şi cu $[5, 4, 1, 3, 2]$, şi cu $[2, 3, 1, 5, 4]$. Nu contează valoarea efectivă atâta timp cât se păstrează proprietatea menţinută anterior. Fie o valoare $r$ pentru care vrem să calculăm răspunsul. Pentru fiecare valoare $a$, din $S$, să considerăm poziţia acesteia din $Cycle(B)$, că $I{~a~}$. Să punem un marker într-un vector paralel cu $Cycle(B)$ pe poziţia $I{~a~} - d{~A~}(r, a)$ pentru fiecare $a$. Este clar că numărul de markere de pe poziţia $I{~r~}$ include un mare număr de elemente din soluţia noastră. Singură problema vine de la valorile $u$ care au $I{~u~} < I{~r~}, $I{~u~} + D_B{~u~} - d{~A~}(r, u} = I{~r~}$ ^({$3$})^ (În termeni mai familiari, $u$ ar ajunge la $r$ "prin spatele ciclului din B"). Pentru a repara această, sugerăm lucrarea pe un vector similar lui $Cycle(B)$, dar care ar repara această problema. Introducem noţiunea şirului $Cycle^2^(B)$, a cărui definiţie este similară, doar că scrierea fiecărui ciclu (că elemente consecutive din parcugerea acestora) este scrisă de două ori (în aceeaşi ordine de fiecare dată). Exemplu: pentru $T = [5, 3, 2, 1, 4], Cycle(T)$ poate fi egal şi cu $[5, 4, 1, 5, 4, 1, 3, 2, 3, 2]$, şi cu $[2, 3, 2, 3, 1, 5, 4, 1, 5, 4]$. Din nou, nu contează cu care varianta lucrăm atâta timp cât se păstrează aceste propietăţi. Continuăm cu noţiunea markerelor, doar că pentru fiecare valoare $a$ din $S$, punem un marker cu $d{~A~}(r, a)$ poziţii înapoi relativ de fiecare apariţie a acesteia din $Cycle^2^(B)$. Acum, este clar că existenţa problematica a unui $u$ menţionat anterior este reparată de apariţia acestuia la cele $D_B{~u~}$ unităţi mai în faţă în şir (într-atât că ^({$3$})^ se respectă). Acum, structura dată (a markerelor) ne poate răspunde corect la queryuri. Singură problema este că această este (în momentul de faţă) descrisă cât să poată să răspundă corect^({$4$})^ doar la queryuri privind pe $r$. Trebuie să reparăm asta. Să presupunem că avem la îndemână un $r'$ care respectă că pentru orice alt $a$ în $S$, $a != r$, avem că $d{~A~}(r,a) ≥ d{~A~}(r, r')$. Atunci, poziţiile markerelor se vor schimbă (dacă am vrem să adaptăm structura noastră de date la a răspunde la queryuri pentru $r'$) asemenea:
# Markerele care proveneau de la valoarea $r$ se duc cu $d{~A~}(r', r)$ pozitii in urma
# Toate celelalte markere se duc cu $d{~A~}(r, r')$ pozitii in fata.
# Markerele care proveneau de la valoarea $r$ se duc cu $d{~A~}(r', r)$ poziţii în urmă
# Toate celelalte markere se duc cu $d{~A~}(r, r')$ poziţii în faţă.
Pentru a putea acomoda aceste operatii, putem folosi trucul detaliat mai atent "aici":https://codeforces.com/blog/entry/58316 (Un vector de frecventa pe care mentinem o variabila globala de lazy care indica cum trebuie sa modificam celelalte valori cu respect fata de operatiile de tipul 2)
Pentru a putea acomoda aceste operaţii, putem folosi trucul detaliat mai atent "aici":https://codeforces.com/blog/entry/58316 (Un vector de frecvenţa pe care menţinem o variabilă globală de lazy care indică cum trebuie să modificăm celelalte valori cu respect faţă de operaţiile de tipul 2)
^({$4$})^: Asta este fals, intr-atat ca daca (pentru $a$ arbitrar din $S$) $D_A{~a~} > D_B{~a~}$, atunci nu este suficient concatenarea de doua ori a ciclurilor cand vrem sa reparam "ciclarea pe la spate", intr-atat ca acest truc a mers doar pentru ca am presupus ca pentru orice $u$, $I{~u~} + D_B{~u~} ≥ I{~r~}$ (vezi ^({$3$})^), intr-atat ca pentru a considera si cazul "ciclarii pe la spate" este necesara o singura parcurgere a acestui ciclu. Asta nu este adevarat daca putem avea valori ale $d{~A~}(r, u) mai mari decat D_B{~u~}$. De aceea, cand calculam raspunsul pentru o multime, vom pune markere intr-un vector paralel cu $Cycle^2^(T)$, unde $T$ este $A$ daca $D_A{~a~} > D_B{~a~}$ (pentru un $a$ din $S$), si $B$ daca nu (cum a fost descris de-a lungul acestui editorial).
^({$4$})^: Asta este fals, într-atât că dacă (pentru $a$ arbitrar din $S$) $D_A{~a~} > D_B{~a~}$, atunci nu este suficient concatenarea de două ori a ciclurilor când vrem să reparăm "ciclarea pe la spate", într-atât că acest truc a mers doar pentru că am presupus că pentru orice $u$, $I{~u~} + D_B{~u~} ≥ I{~r~}$ (vezi ^({$3$})^), într-atât că pentru a consideră şi cazul "ciclarii pe la spate" este necesară o singură parcurgere a acestui ciclu. Asta nu este adevărat dacă putem avea valori ale $d{~A~}(r, u) mai mari decât D_B{~u~}$. De aceea, când calculăm răspunsul pentru o mulţime, vom pune markere într-un vector paralel cu $Cycle^2^(T)$, unde $T$ este $A$ dacă $D_A{~a~} > D_B{~a~}$ (pentru un $a$ din $S$), şi $B$ dacă nu (cum a fost descris de-a lungul acestui editorial).
