の値の小さい順にマス目を黒く塗ることを考えると、塗る過程である部分長方形がすべて黒く塗られ周囲が白く塗られる部分が良い部分長方形となります。
マスを黒く塗ったとき良い部分長方形は高々 つしか新しく現れないので、良い部分長方形をすべて列挙することを考えます。
頂点の空グラフ を考え、あるマスを黒く塗ったときそのマスに辺または角で隣接する既に黒く塗られたマスとの間に辺を追加すると、そのマスを含む の連結成分がマス目上で長方形をなすかを判定すればよく、これは連結成分を UnionFind で管理し連結成分の大きさと上端・下端・左端・右端の座標を持っておくことで可能です。
ある良い部分長方形の容量を計算するには、各行・列で区間最小値を計算するセグメント木やスパーステーブルを持って を計算した後、内側の部分長方形の総和を二次元累積和で求めればよいです。
時間計算量は ) となります。