スタック最小値（蟻本 p.298 で使われるテクニック）を利用した解法です。

左下のマスを固定したときの長方領域の右上

面積の制約を考慮しない場合を考えます。長方形の左下のマスを固定すると、長方領域の右上として採用できるマスは次の図のようになります。

（ここに図があるはずですがリンク切れしていたら教えて下さい）

公式解説のように、マス \((i,j)\) について上に \(h_{i,j}\) 個の . が続いているとします。（\(h_{i,j}\) はDPによって \(O(NM)\) ですべて求められます）

左下マスを \((s_x, s_y)\) として固定したとき、 \(j\) 列目（\(j \ge s_y\)）の右上として採用できるマスが \((s_x, j)\) から上に何個続いているか？は、次のように求められます。

\[\min\{h_{s_x,s_y}, h_{s_x,s_y+1}, \cdots, h_{s_x,j}\}\]

この値は、最小値の更新される場所でしか変化しないので、次のようにブロックとみなして分解することができます。

左下の点を \((s_x,M), (s_x,M-1), \cdots, (s_x,1)\) の順に見ていくとき、このブロックたちをスタックを用いて管理することができ、スタックの push / pop の回数（ブロックの形の変化回数）の合計が \(O(M)\) 回で抑えられます。

\(K=NM\) （長方形の面積の制約がない）の場合、ブロックの面積の合計を別の変数で管理することで、各左下について長方形の右上として採用できるマスの個数を求めることができ、 \(O(NM)\) 時間で答えが求められます。

しかし、 \(K\) が一般の場合、右上のマスによっては面積が大きすぎて採用できない上に、それらを含めてスタックで管理しようとすると、\(s_y\) を1個左にずらしたときに各ブロックの左下のマスとの相対位置は1個右にずれてしまい、ブロックの中のマスを右上にしたときの面積が変化してしまいます。よってさらなる工夫が必要です。

各ブロックの「面積が \(K\) 以下となるマス」の個数を求める

面積が \(K\) 以下となるマスのことを「良いマス」ということにします。

次の図の橙のブロックの中にある良いマスの個数は、下図の「緑のブロックの中にある良いマスの個数」から「紫のブロックの中にある良いマスの個数」を引いたものです。

ここで、緑のブロックと紫のブロックはどちらも左下のマスが固定された \((s_x,s_y)\) となっています。

左下から上に \(k\) マス、右に \(l\) マス伸びた長方形のマスのうち、左下となす長方形の面積が \(K\) 以下のものの個数を \(r_{k,l}\) と表すことにします。\(r_{k, l}\) の値はすべての \(0\le k\le N, 0 \le l \le M\) に対して2次元累積和を用いて \(O(NM)\) 時間で前計算できます。

緑のブロックの右上の座標を \((g_x, g_y)\), 紫のブロックの右上の座標を \((g_x, g'_y)\) とおくと、橙のブロックの中にある良いマスの個数は \(r_{g_x-s_x, g_y-s_y} - r_{g_x-s_x, g'_y-s_y}\) として \(O(1)\) 時間で求められます。

これを先ほどのスタック最小値アルゴリズムに適用すると、左下マスごとにスタックの中のブロックを全部見ることで \(O(NM^2)\) 時間の解法が得られますが、実行時間オーバーとなってしまうのでもう一工夫必要です。

「相対的にブロックが1ずれる」をなんとかしたい

左下のマスの座標を \((s_x,s_y)\) から \((s_x, s_y-1)\) に変えたとき、左下のマスから見たときのブロックの相対的な位置は右にちょうど \(1\) だけずれます。

ここで、前の緑のブロックと紫のブロックの議論において、左下のマスを左に \(1\) 個ずらしたとき、それぞれの長方形の横のサイズが \(1\) 大きくなり、「橙のブロックの答えへの寄与」の合計は次のような形になります：

\[ \begin{aligned} &(r_{s_x, p}-r_{s_x, e})+(r_{s_x,p+1}-r_{s_x,e+1})+\cdots+(r_{s_x,q}-r_{s_x,f})\\ &=(r_{s_x, p}+r_{s_x,p+1}+\cdots + r_{s_x,q})- (r_{s_x,e}+r_{s_x,e+1}+\cdots + r_{s_x,f}) \end{aligned} \]

これは横方向の区間加算であり、 imos 法と相性がいいことに思いを馳せます。「すべての左下マスにおいて \(r_{i,j}\) が合計でいくら加算されるか？」を \(c_{i,j}\) として、\(c\) を imos 法で求めることを考えれば、

• ブロックが追加されたときに \(c_{s_x,p}\) に \(1\) を加え、 \(c_{s_x,e}\) から \(1\) 減らす
• ブロックを削除するときに \(c_{s_x, q+1}\) から \(1\) 減らし、 \(c_{s_x,f+1}\) に \(1\) を加える

ことを行い、すべての処理が終わったあと、 \(i=0,1,\cdots, N\) と \(j=0,1,\cdots, M\) の順に \(c_{i,j+1} += c_{i,j}\) として横方向の累積和を取ると、問題に対する答えを

\[\sum_{i=0}^N \sum_{j=0}^M r_{i,j} c_{i,j}\]

として求めることができます。ブロック追加・削除のときに \(c\) に行う処理は \(O(1)\) 時間であるので、合計で \(O(NM)\) 時間でこの問題を解くことができました。

実装(C++, 280ms)

実装(PyPy3, 832ms)