Solução escrita por Caique Paiva
Conhecimento prévio necessário:
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.