No.025 B

白の濃度をマイナスと考え, 和が $0$ になるかどうかで判断する.

$(1, 1), (i, j)$ を左上, 右下とする矩形の濃度の和 $D(i, j)$ をあらかじめ求めておく.

これは包除原理より

$$D(i,j) = D(i-1,j) + D(i,j-1) - D(i-1,j-1) + C_{i,j}$$

で求められる.

そして $(i_1, j_1), (i_2, j_2)$ を左上, 右下とする矩形を全探索する. この矩形内の濃度も包除原理より

$$D(i_2, j_2) - D(i_1-1, j_2) - D(i_2, j_1-1) + D(i_1-1, j_1-1)$$

で求められる.