Fiecare intrebare poate fi rezolvata in $O(1)$, dar constructia matricei $A$ nu se va incadra in timp pentru testele mari.
Problema poate fi consideranta o varianta clasica a problemei de $RMQ$ in $2D$. Un articol foarte detaliat (in engleza) despre problema $RMQ$ gasiti 'aici':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor. Asadar, pentru a rezolva cazul $2D$ vom folosi ideile care se folosesc in rezolvarea cazului $1D$. Astfel, vom calcula matricea $A$ dar doar pentru laturi puteri ale lui $2$. $A[i][j][k]$ va fi elementul de valoare maxima dintr-un patrat cu coltul stanga-sus pe linia $i$ si coloana $j$ si latura $2^k^$.
$A[i][j][k] = max(A[i][j][k-1], A[i][j+2^k-1^][k-1], A[i+2^k-1^][j][k-1], A[i+2^k-1^][j+2^k-1^][k-1])$

Pentru o raspunde la o intrebare $(i, j, k)$ in $O(1)$ vom determina cea mai mare putere $p$ a lui $2$ astfel incat $2^p^ ≤ k$, si vom lua maximul din $4$ patrate cu colturile in patratul din query si latura $2^p^$.

Pentru o raspunde la o intrebare $i j k$ in $O(1)$ vom determina cea mai mare putere $p$ a lui $2$ astfel incat $2^p^ ≤ k$, si vom lua maximul din $4$ patrate cu colturile in patratul din query si latura $2^p^$. Astfel, raspunsul pentru o intrebare $i j k$ este $max(A[i][j][p], A[i][j+k-2^p^][p], A[i+k-2^p^][j][p], A[i+k-2^p^][j+k-2^p^][p])$.

h2. 'Culori':problema/culori