Codeforces Round #219 (Div. 1) B. Counting Rectangles is Fun
解法
累積和の鬼になります。
- まず, 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; }