h1(#aparate). 'Soluţia':jc2020/solutii/aparate problemei 'Aparate':problema/aparate

h1. 'Soluţia':jc2020/solutii/aparate problemei 'Aparate':problema/aparate

h2. Subtask 1 (10 puncte) - $Q ≤ 1.000$

Putem simula direct toate operaţiile cu brute-force. La un $update$, luăm toate coloanele şi le rotim în $O(N)$ cu $k$ poziţii, iar la un $query$ luăm toate elementele de pe linia $k$ cu coloanele de la $l$ până la $r$ şi le facem suma. Complexitatea pe un $query$ este $O(M)$, iar complexitatea unui $update$ este $O(N * M)$, deci complexitatea totală o să fie $O(Q * N * M)$ pe cel mai rău caz.

h2. Subtask 2 (20 puncte) - $M ≤ 1.000$

Putem să nu facem rotaţiile fizice şi să ţinem minte pentru fiecare coloană cu câte poziţii a fost rotită în sus. Dacă o coloană $c$ a fost rotită în sus cu $k$ poziţii, ca să accesăm elementul de pe linia $l$, putem defapt să accesăm din matricea iniţială elementul de pe linia $(l + k) % N$ şi coloana $c$ (cu precizarea că în soluţie indexăm liniile şi coloanele de la $0$, nu de la $1$).
La un $update$ trebuie doar să actualizăm pentru fiecare coloană cu câte poziţii am rotit-o în sus, iar la un $query$ putem direct să facem suma elementelor cerute.
Astfel complexitatea unui $update$ devine $O(M)$, iar complexitatea unui $query$ devine tot $O(M)$. Astfel, complexitatea finală o să fie $O(Q * M)$.

h2. Subtask 3 (30 puncte) - $N = 2$

Dacă $N = 2$, atunci $M ≤ 50.000$. La acest subtask avem două soluţii.
Prima ar fi să folosim un arbore de intervale pentru a simula operaţiile. Pentru fiecare nod din arborele de intervale (care ţine minte date despre intervalul de coloane $[l, r]$), trebuie să ţinem minte suma elementelor de pe linia 1 cu coloanele din intervalul respectiv, suma elementelor de pe linia 2 cu coloanele din intervalul respectiv, şi un lazy care să ne spună dacă trebuie să interschimbăm cele două linii pe care îl propagăm in fiii nodului. Această soluţie va avea complexitatea $O(Q * logM)$.
O altă soluţie mai uşor de implementat ar fi să grupăm coloanele în grupe de câte $B$ coloane. La un $update$, dacă o grupă este complet inclusă în intervalul respectiv, putem să ţinem minte ca şi la subtaskul 2 o valoare care să ne spună cu cât am rotit toate acele coloane din grupa respectivă. Dacă o grupă de coloane este doar parţial inclusă într-un $update$, putem să rotim fizic (ca şi la subtaskul 1) coloanele care sunt afectate de operaţie. Pentru fiecare grupă trebuie să menţinem şi sumele elementelor de pe fiecare linie. Ca să răspundem la un $query$ luăm toate grupele: dacă o grupă este total inclusă, putem să facem ca şi la subtaskul 2, să vedem care este poziţia adevărată a liniei pe care o vrem, altfel dacă o grupă este inclusa parţial, atunci putem să luăm cu brut elementele din $query$. Complexitatea pentru un $update$ sau un $query$ va fi $O(B * N + M / B)$. Deoarece $N = 2$, complexitatea finală va fi $O(Q * (B * N + M / B))$. Dacă fixăm $B = sqrt(M)$, vom obţine complexitatea finală $O(Q * sqrt(M))$.

h2. Subtask 4 (40 puncte)

La momentul acesta avem foarte multe soluţii care se încadrează în limita de timp pe anumite clase de teste: soluţia de la subtaskul 2 merge bine pe testele cu $M$ mic, dar iese din timp pe celălalte teste, prima soluţie de la subtaskul 3 merge pe teste cu $M$ mare (dacă îl adaptăm să meargă pe teste cu $N > 2$ în complexitate $O(Q * N * logM))$, iar a doua soluţie de la subtaskul 3 merge bine pe testele cu $M$ mare, dar merge prost pe teste cu $M$ mic (asta dacă ne fixăm $B$ la început ca şi o constantă, precum 300, 500 sau 420).
Putem să combinăm mai multe soluţii între ele pentru a obţine soluţii care să se încadreze în limita de timp.