ある整数 \(a \, (1 \leq a \leq N)\) について、\(a\) が書かれたマスを \((i_1, j_1), \dots, (i_n, j_n)\) とおきます。\(a\) が塗りつぶされていないマスに現れない、すなわち \(a\) が書かれたマスが全て塗りつぶされるための条件は、

全ての \(m = 1, \dots, n\) に対し、\(k \lt i_m \leq k+h\) かつ \(l \lt j_m \leq l+w\)

が成り立つことです。\(i_m\) の最小値・最大値を \(\mathrm{min}_{X}, \mathrm{max}_{X}\) とおき、\(j_m\) の最小値・最大値を \(\mathrm{min}_{Y}, \mathrm{max}_{Y}\) とおくと、

\(k \lt \mathrm{min}_{X}\) かつ \(\mathrm{max}_{X} \leq k+h\) かつ \(l \lt \mathrm{min}_{Y}\) かつ \(\mathrm{max}_{Y} \leq l+w\)

と言い換えられます。

よって、全ての \(a = 1, \dots, N\) について \(\mathrm{min}_{X}, \mathrm{max}_{X}, \mathrm{min}_{Y}, \mathrm{max}_{Y}\) を前計算しておくことで、各 \((k, l)\) に対し計算量 \(O(N)\) で答えを求めることができます。

実装例 (C++)

発展問題 : \(1 \leq H, W \leq 2000, 1 \leq N \leq HW\)