No.755
横方向の累積和はあらかじめ計算しておく.
\(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)\) なのでこれで間に合う.