高さを \(h := r_x-l_x+1\)，幅を \(w := r_y-l_y+1\) と定義し，\(h = 1, 2, \dots, N\) の順に，条件を満たす長方形の個数を数えることを考えます．

# の侵食

\(h\) を固定したとき，長方形の上端としてありえるマスは，「自身から自身の下 \(h-1\) マスまで連続して . である」ようなマスです．改めて，そのようなマスが . であり，そうでないマスが # であるとすると，\(h\) を \(1\) 増やすことは，「# が \(1\) マス上に侵食する」ことに相当します．(盤面の外側はすべて # であるものとします．) また，\(h\) を固定したときの答えは，各行における，「. のみからなる長さ \(\lfloor K/h\rfloor\) 以下の区間の個数」となります．

答えを求める

\(h = 1, 2, \dots, N\) と増加させたとき，. のマスが # に変化することは最大 \(NM\) 回発生します．(各マスについて \(1\) 回以下)

. のマスが # に変化したとき，「. の連続する部分」が \(2\) つに分割されることに注目し，以下のアルゴリズムを考えます．

1. 配列 \(cnt[w] := {}\)(. が横にちょうど \(w\) マス連続している部分の個数) を計算する．
2. \(h = 1, 2, \dots, N\) の順に :
   1. \(w_{\max} := \lfloor K/h \rfloor\) とする．
   2. \(w = 1, 2, \dots, M\) の順に，\(\displaystyle cnt[w] \cdot {}\)(長さ \(w\) の区間から長さ \(w_{\max}\) 以下の部分区間を選ぶ方法の数) を答えに加える．
   3. 下のマスが # であるような . のマスを # に変化させ，\(cnt\) を更新する．

このアルゴリズムについて，\(cnt\) の更新以外の部分は \(O(NM)\) 時間で行うことができます．

\(cnt\) の更新には，変化するマスの左右それぞれで最も近い # のマスの位置が求められれば良く，これは

• 平衡二分探索木 (std::set) で \(O(\log M)\) 時間
• word-size tree で \(O(\log_\text{word} M)\) 時間
• bitset で \(O(M / \text{word})\) 時間

で行うことができます．

例えば bitset でこれを行うと，全体で \(O(NM + NM^2 / \text{word})\) 時間となりますが，\(N < M\) なら転置を行うことで，\(M ≤ \sqrt{5 \times 10^6}\) となるため高速です．

実装例 (C++, 113 ms)