Problemă de concurs certificată de InfoAs: Soluțiile tale trimise la această problemă sunt evaluate în exact același mediu ca și la concurs.
RAU Coder 2020 · Clasa a XI-aStructuri de date arborescenteProbleme cu structuri de date
Problema Pixeli
RAU-Gigel este pasionat de grafică, așa că se gândește la un joc cu imagini. El creează într-un editor grafic o imagine bitmap binară de dimensiuni N × N pixeli. O imagine bitmap binară este o matrice de pixeli, fiecare pixel fiind un bit. Să considerăm că valoarea 0 (nesetat) înseamnă alb și valoarea 1 (setat) înseamnă negru (în realitate este exact invers!). Apoi RAU-Gigel împarte imaginea în patru imagini pătrate egale de latură N / 2 pe care le notează de la 1 la 4 (1 este imaginea din colțul dreapta-sus, 2 este cea din colțul dreapta-jos, 3 stânga-jos și 4 stânga-sus). El repetă procedeul pentru fiecare dintre cele 4 imagini obținute, și tot așa, reducând mereu latura la jumătate și notând direcțiile de la 1 la 4, până când ajunge la imagini de mărimea unui pixel.
Pentru simplitate, să presupunem că N este o putere a lui 2, să spunem K. Deci, după K împărțiri succesive de imagini, orice pixel poate fi identificat printr-un șir unic format din cifrele 1, 2, 3 și 4, de lungime K.
De exemplu, dacă N = 4, atunci K = 2. Imaginea inițială are 16 pixeli. Vom avea 2 împărțiri succesive:
După prima împărțire rezultă 4 imagini reduse la jumătate (fiecare are câte 4 pixeli):
4 1
3 2
După a doua împărțire rezultă 16 imagini de câte 1 pixel:
44 41 14 11
43 42 13 12
34 31 24 21
33 32 23 22
Inițial, imaginea este complet albă. Acum începe jocul. RAU-Gigel se gândește la 2 tipuri de operaţii:
- Operaţia
1 xschimbă starea pixelul identificat cu șirulx, descris ca mai sus. Dacă pixelulxnu este setat, îl setează. Dacă pixelulxeste deja setat, atunci îl resetează. - Operaţia
2 x, undexare aceeași semnificație ca mai sus, este o interogare: dacăxeste setat, se răspunde cu0. Dacăxnu este setat, se cere determinarea dimensiunii celei mai mari imagini complet albe, dintre cele create de RAU-Gigel, care conține pixelulx. Dimensiunea este dată de numărul de pixeli conținut.
Cerință
Dându-se N cu semnificația de mai sus și M, reprezentând numărul de operaţii şi cele M operaţii de tipul 1 și 2, să se răspundă la operaţiile de tip 2.
Date de intrare
Fișierul de intrare pixeli.in conține pe prima linie numerele naturale N și M separate cu un spațiu. Pe următoarele M linii se află câte o cifră de 1 sau 2 și câte un string, de forma tip_operaţie x, reprezentând tipul operaţiei şi șirul x.
Date de ieșire
Fișierul de ieșire pixeli.out va conține răspunsurile pentru operaţiile de tip 2, câte unul pe linie.
Restricții și precizări
2 ≤ N ≤ 2.000.000.0001 ≤ M ≤ 10.000- În toate testele,
Neste o putere a lui2 - Toate șirurile
xsunt corect definite - Pentru teste în valoare de 30 de puncte,
N ≤ 1.000șiM ≤ 50
Exemple
4 11 1 11 1 22 2 22 2 33 2 44 2 24 1 22 2 22 2 24 1 11 2 44
0 4 4 1 4 4 16
8 9 1 111 1 222 2 222 2 333 2 444 2 242 1 222 2 222 2 242
0 16 16 4 16 16
Explicația exemplelor
Explicația primului exemplu
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
După primele 2 operații de tip 1, imaginea va conține:
0 0 0 1
0 0 0 0
0 0 0 0
0 0 0 1
Următoarele 4 interogări vor referi, în ordine, pixelii marcați cu a, b, c, d (imaginea de mai jos). Cum a era setat, răspunsul este 0. Cea mai mare imagine albă, creată de RAU-Gigel, care conține b, este colțul stânga jos cu 4 pixeli. La fel pentru c. În cazul pixelului d, răspunsul este 1 (chiar el).
c 0 0 e
0 0 0 0
0 0 0 0
b 0 0 a
Urmează o operație de tip 1 care resetează pixelul notat cu a (șirul 22). Următoarele 2 interogări pentru a și d generează răspunsurile 4, respectiv 4.
În final, se resetează și pixelul e, iar ultima interogare, pentru c, va determina răspunsul 16, toată imaginea fiind acum complet albă.
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;