公式解説では直接答えへの寄与を求めていますが，各 \(n,m\ (1\leq n\leq N,1\leq m\leq M)\) について縦 \(n\)，横 \(m\) の長方形の個数を列挙することが同じく \(O(NM)\) 時間で行えます．

公式解説と同様に下の辺が含まれる行を固定して，上に連続する . の個数 \(h\) を求めておきます．

行方向に切って分割すると，部分長方形の上の辺に着目して数え上げることができます．

例えば

...#..#...
.......#.#
.#........
.....#....
..........

については以下のように分割します．

分割の計算は Cartesian Tree を用いてもよいですし，用いずとも stack によって計算できます（実装例は stack による実装です）．

分割のうち下から \(l\) 行目〜 \(r\) 行目 \((1\leq l\leq r)\) に渡り，幅が \(w\) のブロックからの寄与を考えます．

• 上の例での各ブロックについては \((l,r,w)=(1,1,10),(2,2,5),(3,4,3),(2,3,4),(4,4,1)\) です．

そのブロックに上の辺が含まれるような高さ \(i\)，幅 \(j\) の部分長方形は \(l\leq i\leq r,1\leq j\leq w\) について \(w-j+1\) 個存在します．

従って各サイズの部分長方形の個数のすべてのブロックについての総和は，二次元累積和を用いれば \(O(NM)\) 時間で計算できます．

実装例(C++)