CF372B Counting Rectangles is Fun

有一个 $n \times m$ 的矩形网格，每个格子中包含一个整数：$0$ 或 $1$。称第 $i$ 行第 $j$ 列的格子为 $(i, j)$。 定义“矩形”为四个整数 $a, b, c, d$（$1 \le a \le c \le n$；$1 \le b \le d \le m$）。该矩形表示网格中的一组格子 $\{(x, y) : a \le x \le c, \, b \le y \le d\}$。定义“好矩形”为只包含 $0$ 的矩形。 你需要回答以下 $q$ 个查询：计算所有格子都在给定矩形内的好矩形的数量。

第一行有三个整数：$n, m$ 和 $q$（$1 \le n, m \le 40$，$1 \le q \le 3 \times 10^5$）。接下来的 $n$ 行，每行包含 $m$ 个字符，表示网格。网格的行从上到下编号，列从左到右编号，行和列均从 $1$ 开始编号。 接下来的 $q$ 行，每行包含一个查询：四个整数，表示当前矩形的 $a, b, c, d$（$1 \le a \le c \le n$；$1 \le b \le d \le m$）。

对于每个查询，输出一个答案，每个答案占一行。

对于第一个样例，有一个 $5 \times 5$ 的矩形网格，第一个、第二个和第三个查询如下图所示。  - 对于第一个查询，共有 $10$ 个好矩形：五个 $1 \times 1$、两个 $2 \times 1$、两个 $1 \times 2$ 以及一个 $1 \times 3$。 - 对于第二个查询，只有一个 $1 \times 1$ 的好矩形。 - 对于第三个查询，共有 $7$ 个好矩形：四个 $1 \times 1$、两个 $2 \times 1$ 以及一个 $3 \times 1$。 由 DeepSeek-V3.2 翻译。