Codeforces Round #219 (Div. 1) B. Counting Rectangles is Fun

問題

codeforces.com

解法

累積和の鬼になります。

• まず, ok[y1][x1][y2][x2] = (長方形 (y1, x1, y2, x2) が good rectangle であるかどうか) というのを考えたいですが, これは長方形 y1, x1, y2, x2 内の値の cell の値の合計が 0 であれば良くて, これは前計算で cnt[y][x] = (左上から 点(y, x) までの cell の値の合計)というのを求めておけば, O(1) で判定できます。これはよくあるやつ。

• 次に, rui[y][x][yy][xx] = ((yy, xx) を右下にする, 左上の上限が (y, x) までの, good rectangle となる長方形の数) というのを求めます。ans[y][x][yy][xx](各クエリで答えるやつ) というのは, Y = y, y+1, ..., yy で X = x, x+1, ..., xx とした時の, rui[y][x][Y][X] の和ですね。
  • rui が求まれば, ans は, ans[y][x][yy][xx] = ans[y][x][yy][xx-1] + ans[y][x][yy-1][xx] - ans[y][x][yy-1][xx-1] + rui[y][x][yy][xx] で求められますね(要するに今まで計算してたやつに, (yy, xx) の結果を追加する感じ)。
  • rui の計算は, ans とは逆順に計算する感じです。今まで計算していたやつに, (y, x) の結果を追加するイメージで, 更新式は rui[y][x][yy][xx] = rui[y][x+1][yy][xx] + rui[y+1][x][yy][xx] - rui[y+1][x+1][yy][xx] + ok[y][x][yy][xx] となります。

string field[44];
int cnt[44][44];
int ok[44][44][44][44];
// rui[y][x][yy][xx]: (yy, xx) を右下にする, 左上の上限が (y, x) までの, ok になるやつの数
int rui[44][44][44][44];
int ans[44][44][44][44];

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < n; i++) cin >> field[i];
    for (int y = 1; y <= n; y++) for (int x = 1; x <= m; x++) {
        cnt[y][x] = cnt[y-1][x] + cnt[y][x-1] - cnt[y-1][x-1] + (field[y-1][x-1]-'0');
    }
    for (int y1 = 1; y1 <= n; y1++) for (int x1 = 1; x1 <= m; x1++) {
        for (int y2 = y1; y2 <= n; y2++) for (int x2 = x1; x2 <= m; x2++) {
            ok[y1][x1][y2][x2] = (cnt[y2][x2]-cnt[y2][x1-1]-cnt[y1-1][x2]+cnt[y1-1][x1-1] == 0);
        }
    }
    for (int yy = 1; yy <= n; yy++) for (int xx = 1; xx <= m; xx++) {
        for (int y = yy; y >= 1; y--) for (int x = xx; x >= 1; x--) {
            rui[y][x][yy][xx] = rui[y][x+1][yy][xx] + rui[y+1][x][yy][xx] - rui[y+1][x+1][yy][xx] + ok[y][x][yy][xx];
        }
    }
    for (int y = 1; y <= n; y++) for (int x = 1; x <= m; x++) {
        for (int yy = y; yy <= n; yy++) for (int xx = x; xx <= m; xx++) {
            ans[y][x][yy][xx] = ans[y][x][yy][xx-1] + ans[y][x][yy-1][xx] - ans[y][x][yy-1][xx-1] + rui[y][x][yy][xx];
        }
    }
    while (q--) {
        int a, b, c, d;
        scanf("%d %d %d %d", &a, &b, &c, &d);
        printf("%d\n", ans[a][b][c][d]);
    }
    return 0;
}