\(N,M \leq 10^5\) かつグリッド全体ではなく\(K\leq 10^5\) 個の黒いマスの 位置が与えられている場合でも高速に解くことができる方法を解説します．

kyopro_friendsさんの解説と同様にグリッドをずらして考えます．さらに下と右に黒埋めておきます．(実はこの解法では右に埋める操作は必要ありません)

....#          #          #
...#.         ..         .#
..#..   →    .#.    →   .##
.#.#.       ....       ..##
#...#      ..###      ..###
           ....       ..##
           .#.        .##
           ..         .#
           #          #

これは \(A_i\leq C_i\leq B_i\)となる 単調増加数列 \(C\) の個数を求められれば解くことができます．

この例では，

• 1列目は \(1\leq C_1 \leq 5\)
• 2列目は \(3\leq C_2 \leq 6\)
• 3列目は \(5\leq C_3 \leq 7\)
• 4列目は \(7\leq C_4 \leq 8\)
• 5列目は \(9\leq C_5 \leq 9\)

となる単調増加数列 \(C\)が数えられれば良いです．

このような数え上げは \(\textrm{O}(K+(N+M)\log^2(N+M))\) で計算することができます．

解説

実装例