Vom reprezenta harta ca o matrice a cu n linii si m coloane cu componente de tip imobil.
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.
|