Tipul imobil este o structura īn care retinem 3 cāmpuri:

– nrmax (numarul maxim de apartamente din imobilul respectiv, sau –1 daca īn pozitia respectiva nu exista un imobil);

– nr (numarul de apartamente īnchiriate din imobilul respectiv, sau –1 daca īn pozitia respectiva nu exista un imobil);

– p (pretul cu care se īnchiriaza un apartament īn acel imobil).

Problema presupune implementarea a 3 operatii:

1. īnchirierea unui apartament īntr-un anumit imobil (cāmpul nr corespunzator imobilului va creste cu 1).

2. eliberarea unui apartament īntr-un anumit imobil (cāmpul nr corespunzator imobilului va scadea cu 1).

3. determinarea venitului īntr-o zona dreptunghiulara data si afisarea acestuia.

Observati ca zona dreptunghiulara este specificata prin doua colturi opuse (dar nu neaparat coltul din stānga-sus si cel din dreapta-jos; acestea doua trebuie determinate).

I. Pentru a determina venitul, o prima idee ar fi sa parcurgem zona dreptunghiulara specificata si sa īnsumam veniturile obtinute din īnchirieri la imobilele din zona.

Complexitatea acestei abordari este nr_operatii_tip_3 * n * m.

II. O a doua idee este de a retine niste sume partiale

Sum[i][j]= venitul obtinut din īnchirierea apartamentelor din imobile situate īn zona cu coltul stānga-sus īn (1,1), iar coltul dreapta-jos īn (i,j).

Cunoscānd aceste sume partiale, determinarea venitului pentru dreptunghiul cu coltul stānga-sus īn (x1,y1) si coltul dreapta-jos īn (x2,y2) se face īn O(1) astfel:

long venit (int x1, int y1, int x2, int y2)

{return Sum[x2][y2]-Sum[x2][y1-1]-Sum[x1-1][y2]+Sum[x1-1][y1-1]; }

Dar la īnchirierea/eliberarea unui apartament aceste sume partiale trebuie actualizate (actualizari care se realizeaza īn O(nxm)).

III.

Pentru a executa eficient operatiile de actualizare/determinare venit vom utiliza arbori indexati binar.

Mai exact, vom retine niste sume partiale īn matricea Sum cu n linii si m coloane astfel:

Sum[i][j]=venitul obtinut din imobilele din dreptunghiul cu coltul din stānga-sus (i-2k+1, j-2t+1), unde k = numarul de zerouri finale din reprezentarea binara a lui i, iar t reprezinta numarul de zerouri finale din reprezentarea binara a lui j; coltul din dreapta-jos este (i,j).

Pentru a calcula venitul din dreptunghiul cu coltul stānga-sus īn (x1,y1) si cotul din dreapta-jos īn (x2,y2), vom utiliza o formula similara cu cea de la ideea II:

unsigned long venit (int x1, int y1, int x2, int y2)

{return s(x2,y2)-s(x2,y1-1)-s(x1-1,y2)+s(x1-1,y1-1); }

De data aceasta am utilizat o functie s(x,y) care determina pe baza sumelor partiale memorate īn Sum venitul din zona cu coltul stānga-sus īn (1,1) si coltul dreapta-jos īn (x,y).

long s (int x, int y)

{long val=0;

int nr0i=0, nr0j, i, j;

for (i=x; i>0; i-=1<<nr0i, nr0i++)

{for (j=y, nr0j=0;j>0; j-=1<<nr0j, nr0j++)

{

val+=Sum[i][j];

while (!(j & 1<<nr0j)) nr0j++;

}

while (!(i & 1<<nr0i)) nr0i++;

}

return val;

}

Observati ca īn acest caz complexitatea este O(log n x log m).

Operatiile de īnchiriere/eliberare apartament presupun acutalizarea sumelor partiale memorate īn matricea Sum (cu o valoare pozitiva sau negativa):

void actualizare (int x, int y, long val)

{

int nr0i=0, nr0j, i, j;

for (i=x; i<=n; i+=1<<nr0i)

{for (j=y, nr0j=0;j<=m; j+=1<<nr0j)

{

Sum[i][j]+=val;

while (!(j & 1<<nr0j)) nr0j++;

}

while (!(i & 1<<nr0i)) nr0i++;

}

}

Observati ca si īn acest caz complexitatea este O(log n x log m).

Deci complexitatea algoritmului este O(nr_operatii x log n x log m).

Din cauza dimensiunii, ultmele doua teste lipsesc din arhiva de teste. Le pot trimite prin email, la cerere.