二次元累積和と二分探索を用いた、想定解とは異なる解法を説明します。

\(H \times W\) の2次元配列 \(a\) を次のように定めます。

• \(a_{i,j}=\left\{ \begin{array}{ll} 0& グリッドのマス (i, j)に穴がない\\ 1 & グリッドのマス (i, j)に穴がある \end{array} \right. \)

こうすると、左上のマスが \((i, j)\) 、右下のマスが \((i + n - 1, j + n - 1)\) である正方形に穴がないことと、\(\displaystyle \sum_{x = i}^{i + n - 1} \sum_{y = j}^{j + n - 1} a_{x, y} = 0\) であることが同値となります。\(a\) の二次元累積和を構築することで、\((i, j, n)\) が与えられた時の \(\displaystyle \sum_{x = i}^{i + n - 1} \sum_{y = j}^{j + n - 1} a_{x, y}\) の値は \(O(1)\) で求めることができます。

これから、答えを数えていきます。左上のマス \((i, j)\) を固定して、左上が \((i, j)\) となるような穴のない正方形を探索しましょう。次の判定問題を考えます:

• 左上が \((i, j)\) である一辺が \(k\) の穴のない正方形を作れるか？

この判定問題は \(k\) について単調です。つまり、\(k \geq 2\) について、一辺が \(k\) の正方形を作れるなら、一辺が \(k - 1\) の正方形を作ることができます。

判定問題の答えが Yes となる最大の \(k\) を \(K\) とすると、左上が \((i, j)\) であるような正方形は、一辺の長さが \(1, 2, \dots, K\) の \(K\) 個作ることができるため、答えに \(K\) を足せばよいことになります。

\(K\) を求めるためには、二分探索が有効です。判定問題は先述の通り二次元累積和で \(O(1)\) で解けて、\(K\) の上界を\(\min(H, W)\) として取ることができるので、\(K\) は \(O( \log (\min(H, W))\) で求めることができます。

後は、これをすべての \((i, j)\) について求め、答えを足し合わせれば最終的な答えとなります。\((i, j)\) の組は \(\Theta(HW)\) 個なので、全体の計算量は \(\Theta(HW \log (\min(H, W))\) です。想定解より計算量は悪化しますが、この問題の制約下で \(HW \log (\min(H, W)) \leq 1.4 \times 10^8\) と見積もれるので、定数倍に注意すれば十分ACできる範囲内です。