\(O(ab)\) による二次元累積和を前準備で用いることで、部分長方形が含む \(-1\) の数と \(c_{i,j}\) の合計を部分長方形 \(1\) つにつき \(O(1)\) で入手することができます。
よって、この問題は \(O(ab)\) で解くことができました。