Zero-Sum Rectangle [yukicoder No.755] - はまやんはまやんはまやん

前提知識

累積和とimos法

考察過程

1. これはyukicoder特有のテクだが、pypyで通るよと言っている問題は怪しい計算量だけどそれでいいよというメッセージ
2. クエリ毎に長方形を数えるような問題は過去出会ったことが無いので、別の方法を考える
3. とりあえずループで回す対象を探すが、長方形の全探索は120^4でギリギリ間に合いそうな雰囲気がある
4. yukicoder特有の枕詞もあったので、この方針で考える
5. すると、ある長方形での総和が0であれば、この長方形に含まれる座標すべて+1することで、クエリに答えられると分かる
6. ある長方形での総和を求めるには累積和、長方形に含まれる座標すべて+1するにはimos法を使えば間に合う

解法

https://yukicoder.me/submissions/303540

すべての長方形を全探索して配列ansを作ろう。
ans[y][x] := マス(x,y)が含まれる、総和が0の長方形の個数
ある長方形について二次元累積和を使って総和が0であるかを判定しよう。
もし総和が0であれば、その長方形に含まれるマスはすべて+1されるので、二次元imos法で+1しよう。
最後のN個のマスについて答える問題はans配列があれば、ans[y][x]を答えるだけ。

int N, M, A[150][150];
Ruisekiwa2D<150, 150> r2d;
int ans[150][150];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(y, 0, M) rep(x, 0, M) cin >> A[y][x];

    rep(y, 0, M) rep(x, 0, M) r2d.set(y, x, A[y][x]);
    r2d.build();

    rep(sy, 0, M) rep(ty, sy, M) rep(sx, 0, M) rep(tx, sx, M) {
        if (r2d.get(sx, sy, tx, ty) == 0) {
            ans[sy][sx]++;
            ans[ty + 1][sx]--;
            ans[sy][tx + 1]--;
            ans[ty + 1][tx + 1]++;
        }
    }

    rep(y, 0, M) rep(x, 1, M) ans[y][x] += ans[y][x - 1];
    rep(x, 0, M) rep(y, 1, M) ans[y][x] += ans[y - 1][x];

    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        x--; y--;
        printf("%d\n", ans[y][x]);
    }
}