各\((k, l)\)について、領域\((k, k + h]\times(l, l + w]\)の内側にのみ存在する整数の種類数を求めることを考えます。(最終的な答えはここで求める種類数を全種類数から引いたものになります。)

マス\((i, j)\)を塗りつぶすような\((k, l)\)の領域は\([i - h, i)\times[j - w, j)\)なので、
ある整数\(a\)について、\(a\)が書かれているマスを全て塗りつぶすような\((k, l)\)の領域は\(\bigcap_{A_{i, j} = a}[i - h, i)\times[j - w, j)\)です。

各整数\(a\)について上記の領域を求めると、これは\([0, H - h]\times[0, W - w]\)上の長方形領域となります。各整数について2次元imos法を使ってこの長方形領域に対する加算をおこなう解法は\(O(HW + N)\)となりますが、実際にはマス上に存在する整数についてのみ考えれば良いので計算量は\(O(HW)\)となります。

実装例