青木君は白いスタンプを使って、高橋君が黒く塗りつぶしたマスを白く塗り替えようとします。一度黒く塗られた後に白に「塗り替え」られる部分は長方形領域をなします。
もし \(h_1 < h_2\) であっても、青木君が黒から白に「塗り替え」ることができる部分の行数は \(h_1\) より大きくはなりません。よって、\(h_1 < h_2\) のときは \(h_2\) を \(h_1\) と同じ値に置き換えても問題の答えは変わりません。 同様に、\(w_1 < w_2\) のときは、\(w_2\) を \(w_1\) と同じ値に置き換えても問題の答えは変わりません。
したがって、以下では \(h_1 \geq h_2\) かつ \(w_1 \geq w_2\) が成り立つと仮定します。

この仮定の元で青木君は、白いスタンプを押す長方形を、高橋君が黒く塗った長方形からはみ出さないように選ぶことができます。
黒く塗られた長方形からはみ出すように白いスタンプを押すのは、明らかに青木君にとって最適ではないため、以下では「青木君は必ず、高橋君がスタンプを押した長方形からはみ出さないようにスタンプを押す」と仮定しても問題ありません。
すなわち、「高橋君がマス \((i_T, j_T)\) を左上とする長方形にスタンプを押したとき、青木君は \(i_T \leq i_A \leq i_T+h_1-h_2\) かつ \(j _T\leq j_A \leq j_T + w_1-w_2\) を満たすマス \((i_A, j_A)\) を左上とする長方形のみにスタンプを押す」と仮定します。

まず、本問題の答えを求めるためのいくつか前計算について、次で述べます。

・前計算

(a) \(A_{i, j}\) の二次元累積和 \(\mathrm{sum}[\ast][\ast]\)

まず、\(A_{i, j}\) の二次元累積和 \(\mathrm{sum}[\ast][\ast]\) を計算しておきます。 すなわち、\(0 \leq i \leq H\) かつ \(0 \leq j \leq W\) を満たすすべての整数の組 \((i, j)\) について、

\(\mathrm{sum}[i][j] := \displaystyle\sum_{i' = 0}^i \displaystyle\sum_{j'=0}^j A_{i', j'}\)

を計算しておきます。
\(\mathrm{sum}[\ast][\ast]\) の計算は、\(1 \leq i \leq H\) かつ \(1 \leq j \leq W\) を満たす整数の組 \((i, j)\) について、

\(\mathrm{sum}[i][j] = \mathrm{sum}[i-1][j] + \mathrm{sum}[i][j-1] - \mathrm{sum}[i-1][j-1] + A_{i, j}\)

であることを用いて、\(\mathrm{O}(HW)\) 時間で行うことができます（ただし、上式では \(i = 0\) または \(j = 0\) のときは \(A_{i, j} := 0\) とします）。

(b) 高橋君・青木君がスタンプで塗りつぶす長方形内の \(A_{i, j}\) の総和 \(\mathrm{Taka}[\ast][\ast], \mathrm{Aoki}[\ast][\ast]\)

「高橋君がマス \((i_T, j_T)\) を左上とする長方形にスタンプを押すときの、その長方形内に書かれた整数の総和」を \(\mathrm{Taka}[i_T][j_T] \)とおきます。
すなわち、\(1 \leq i_T \leq H-h_1+1\) かつ \(1 \leq j_T \leq W-w_1+1\) を満たす整数の組 \((i_T, j_T)\) に対し、\(\mathrm{Taka}[i_T][j_T]\) を、

\(\mathrm{Taka}[i_T][j_T] := \displaystyle \sum_{i = i_T}^{i_T+h_1-1} \displaystyle\sum_{j = j_T}^{j_T+h_1-1} A_{i, j} \)

で定めます。

青木君に対しても同様に、「青木君がマス \((i_T, j_T)\) を左上とする長方形にスタンプを押すときの、その長方形内に書かれた整数の総和」を \(\mathrm{Aoki}[i_A][j_A]\) とおきます。
すなわち、\(1 \leq i_A \leq H-h_2+1\) かつ \(1 \leq j_A \leq W-w_2+1\) を満たす整数の組 \((i_A, j_A)\) に対し \(\mathrm{Aoki}[i_A][j_A]\) を、

\(\mathrm{Aoki}[i_A][j_A] := \displaystyle \sum_{i = i_A}^{i_A+h_2-1} \displaystyle\sum_{j = j_A}^{j_A+h_2-1} A_{i, j} \)

で定めます。

\(\mathrm{Taka}[\ast][\ast]\) と \(\mathrm{Aoki}[\ast][\ast]\) は、先述の二次元累積和 \(\mathrm{sum}[\ast][\ast]\) を活用することにより、\(\mathrm{O}(HW)\) 時間で計算できます。

・本問題の答えを計算する方法

上で前計算した \(\mathrm{Taka}[\ast][\ast]\) と \(\mathrm{Aoki}[\ast][\ast]\) を用いて、本問題の答えを計算する方法を以下で述べます。

高橋君がスタンプを押す長方形の左上のマス \((i_T, j_T)\) を固定したとき、青木君が最適な行動を取るとスコアがいくらになるかを考えます。
まず、高橋君がスタンプを押すことで、黒く塗られたマスに書かれた整数の総和は \(\mathrm{Taka}[i_T][j_T]\) になります。
その後、青木君がマス \((i_A, j_A)\) を左上とする長方形にスタンプを押すと、黒く塗られたマスに書かれた整数の総和は \(\mathrm{Taka}[i_T][j_T] - \mathrm{Aoki}[i_A][j_A]\) となりますが、青木君はこの値が最小となるように（かつ、高橋君がスタンプを押した長方形からはみ出ないように）スタンプを押すので 「高橋君がマス \((i_T, j_T)\) を左上とする長方形にスタンプを押した後青木君が最適な行動を取るときのスコア \(\mathrm{score}[i_T][j_T]\) 」は

\(\mathrm{score}[i_T][j_T] = \mathrm{Taka}[i_T][j_T] - \displaystyle\max_{\substack{i_T \leq i_A \leq i_T+h_1-h_2\\ j _T\leq j_A \leq j_T+w_1-w_2}} \mathrm{Aoki}[i_A][j_A]\)

となります。

実際のゲームでは、高橋君はこの値が最大となるようにマス \((i_T, j_T)\) を選ぶので、本問題の答えは「高橋君が選ぶことができるすべてのマス \((i_T, j_T)\) にわたる、\(\mathrm{score}[i_T][j_T]\) の最大値」です。
つまり、\(1 \leq i_T \leq H-h_1+1\) かつ \(1 \leq j_T \leq W-w_1+1\) を満たすマス \((i_T, j_T)\) すべてについて \(\mathrm{score}[i_T][j_T]\) を計算し、その中の最大値を取れば本問題の答えが得られます。

\(\mathrm{score}[i_T][j_T]\) の計算に必要な値のうち、\(\mathrm{Taka}[\ast][\ast]\) はすでに計算済みなので、 \(1 \leq i_T \leq H-h_1+1\) かつ \(1 \leq j_T \leq W-w_1+1\) を満たすすべてのマス \((i_T, j_T)\) ついて、

\(M[i_T][j_T] := \displaystyle\max_{\substack{i_T \leq i_A \leq i_T+h_1-h_2\\ j _T\leq j_A \leq j_T+w_1-w_2}} \mathrm{Aoki}[i_A][j_A]\)

の値がわかればこの問題を解くことができます。 したがって、以下でこれを十分高速に求める方法を述べます。

・\(M[\ast][\ast]\) を十分高速に計算する方法

直感的には、\(M[i][j]\) はマス \((i, j)\) を左上、マス \((i+h_1-h_2, j+w_1-w_2)\) を右下とする長方形内の、\(\mathrm{Aoki}[\ast][\ast]\) の要素の最大値です。
これを求めるために、まず \(\mathrm{Aoki}[\ast][\ast]\) の各行について、横方向に最大値の計算を行って二次元配列 \(M'[\ast][\ast]\) を作り、その後この二次元配列 \(M'[\ast][\ast]\) の各列に対して縦方向に最大値の計算を行います。

つまり、まず各 \(i = 1, 2, \ldots, H\) について、下記の \(M'[i][\ast]\) を計算します。

\(M'[i][j] := \displaystyle\max_{ j \leq j' \leq j + w_1-w_2} \mathrm{Aoki}[i][j'], \,\,\text{for}\,\,j = 1,2,\ldots, W-w_1+1\)

その後、これを用いて 各 \(j = 1, 2, \ldots, W - w_1+1\) について、\(M[\ast][j]\) を下記の式によって計算します。

\(M[i][j] = \displaystyle\max_{i \leq i' \leq i+h_1-h_2} \Big(\displaystyle\max_{ j \leq j' \leq j+w_1-w_2} \mathrm{Aoki}[i'][j']\Big) = \displaystyle\max_{i \leq i' \leq i+h_1-h_2} M'[i'][j], \,\,\text{for}\,\,i = 1, 2, \ldots, H-h_1+1\)

ここで、各 \(i = 1, 2, \ldots, H\) について \(\mathrm{Aoki}[i][\ast]\) から \(M'[i][\ast]\) を十分高速に計算するためには、

• 両端キューを用いたスライド最小値
• Sliding Window Aggregation (SWAG)
• セグメント木
• Sparse Table

などを用いればよいです。 また同様の方法で、各 \(j = 1, 2, \ldots, W-w_1+1\) について \(M'[\ast][j]\) から \(M[\ast][j]\) を十分高速に計算することもできます。

以上で、本問題を \(\mathrm{O}(HW)\) 時間または \(\mathrm{O}(HW(\log H + \log W))\) 時間で解くことができます。

・スライド最小値について

長さ \(N\) の配列 \(A[0], ..., A[N-1]\) とパラメータ \(K\) が与えられたとき、\(A[i]\) の値を現在の \(\min \{ A[i], ..., A[\min(i+K, N-1)] \}\) で置き換えたいとします。

\(K = 1\) なら簡単です。

for(i=0;i+1<N;i++) A[i] = min(A[i], A[i+1]);

\(K = 7\) のとき、\(7\) 以下の非負整数は \(\{ 1, 2, 4 \}\) の subset の和として表せるので以下のように求まります。

for(i=0;i+1<N;i++) A[i] = min(A[i], A[i+1]);
for(i=0;i+2<N;i++) A[i] = min(A[i], A[i+2]);
for(i=0;i+4<N;i++) A[i] = min(A[i], A[i+4]);

一般の場合も同様に求まります。

while(K > 0){
	int d = (K + 1) / 2;
	for(i=0;i+d<N;i++) A[i] = min(A[i], A[i+d]);
	K -= d;
}