Solução Informática - Nível Intermediário - Semana 36

Solução escrita por Caique Paiva

Conhecimento prévio necessário:

• Somas de Prefixos

A ideia principal é a seguinte: Se um quadrado (i, j) é uma joia, então, quantas quadruplas $(i, j, k, l)$ existem, com esse $i, j$ fixo? A resposta é a quantidade de $O$ na linha $i$ depois de $(i, j)$ vezes a quandidade de $I$ na coluna $j$ depois de $(i, j)$. Por exemplo, para $(2, 2)$ no exemplo abaixo, temos $2$ $O$ na linha $2$ depois de $(2, 2)$, e temos $2$ $I$ na coluna $2$ depois de $(2, 2)$, então, a resposta para essa quadrupla é $4$.

Então, sendo $q_{i, j}$ a resposta dessa pergunta para o par $(i, j)$, a resposta do problema vai ser a soma de todas essas respostas. Portanto, podemos calcular essa soma de valores em $O(HW)$, então, se conseguirmos responder essa pergunta em $O(1)$, o problema está resolvido, e nós conseguimos responder essa pergunta em $O(1)$ com uma prefix sum! Seja $pref[N][N]$ um vetor que, na posição $(i, j)$, $pref[i][j]$ guarda a quantidade de $O$ na linha $i$ depois de $j$. Veja que $pref[i][n] = 0$ e que $pref[i][j] = pref[i][j+1] +$ (Se $(i, j+1)$ é $O$). Então, conseguimos calcular esse valor em $O(HW)$. Para fazer a prefix sum das colunas $j$, é análogo.

Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.