横方向の累積和はあらかじめ計算しておく.

\(x_i, y_i\) を読み, 長方形の左端と右端を \(l, r \ (l \leq x_i \leq r)\) とする. そして,

\[B_i = \left\{ \sum_{j=l}^r A_{i, j} \right\}\]

という数列を計算する. これはあらかじめ計算しておいた累積和を使う.

そして, \(B_{y_i+1} \dots B_M\) の部分について累積和を計算し, 出現する数値の正負を反転したものの個数を連想配列に入れる.

続いて, \(B_{y_i}\) から始めて \(B_{y_i-1}, B_{y_i-2}\) の順に足していき, 上で計算した出現する数値の個数を足していく.

これをすべての \(l, r\) で行う.

計算量は \(O(M^3N)\) なのでこれで間に合う.