あるマスに2手以内でたどり着く方法は

・下に移動してから右に移動する

・右に移動してから下に移動する

のどちらかしかありません(各移動は0マスでもよい)。それぞれの方法で到達できるマスの数を求めて合計することを考えます。どちらの方法でも到達できるマスが存在するので、そのようなマスを重複して数えないように工夫する必要があります。

後者の方法で到達できるマスについては、各列で最も上にある障害物の位置を求めることで \(O(M+W)\) で求めることができます。

前者も同様に求めることができますが、そのうち後者の移動では到達できないマスだけを数える必要があります。そのようなマスであることは、自身より上に障害物があることと同値です（1行目は、最も左にある障害物より右の全てのマスに障害物があるとみなします）。

よって、上の行から順に、各列について障害物が既に登場したかをセグメントツリー/Binary Indexed Treeを用いて記録しながら計算することで \(O((H+M)\log W)\) で求めることができます。