时间限制	内存限制
`1000 ms`	`65536 KB`

# 题目描述

我们都知道，扫雷游戏中某些格子是雷，其它格子是空的。这个时候空的格子会显示出以它为中心的九宫格中雷的数量。

现在给定一张 $n \times m$ 的 $01$ 图 $Y$ ， $1$ 代表这个格子是雷， $0$ 代表这个格子是空的。进行 $q$ 次询问，每次询问给定 $x_1, y_1, x_2, y_2$ ，表示一个子矩阵的左上角和右下角坐标，每次用这个子矩阵生成一张扫雷图，进而得出每个空格应填入什么数（注意，在子矩阵外面的雷不应该计入这些空格里的数）。询问这个子矩阵中所有空格的数字之和。

# 输入格式

第一行给出三个正整数 $n, m, q$ ，分别代表了 $Y$ 的行数， $Y$ 的列数以及询问次数。其中， $1 \le n \times m \le 3 \times 10^5$ ， $1 \le q \le 3 \times 10^5$ 。

随后 $n$ 行，对于第 $i$ 行，将给出 $m$ 个整数 $a \in [0, 1]$ ，代表 $Y$ 第 $i$ 行中雷的分布情况。其中，第 $j$ 个数字代表了第 $i$ 行第 $j$ 列是否为雷，若 $a = 0$ 代表此格无雷，若 $a = 1$ 代表此格有雷。

随后 $q$ 行，每行给出四个正整数 $x_1, y_1, x_2, y_2$ ，代表了选择 $Y$ 的第 $x_1$ 行第 $y_1$ 列到第 $x_2￥行第 $y_2$ 列这一个小矩形来生成对应的数字。其中， $1 \le x_1 \le x_2 \le n$ ， $1 \le y_1 \le y_2 \le m$ 。

# 输出格式

$q$ 行整数，为每种雷型生成的数字之和。

两次询问之间用换行间隔。

具体含义见题目描述。

# 样例输入

	5 5 3
	1 0 1 1 0
	0 0 0 0 0
	1 0 1 0 1
	1 1 1 0 0
	0 0 1 1 1
	1 1 2 3
	1 1 5 5
	3 2 3 4

# 样例输出

	6
	41
	2

# 样例解释

在样例解释中，用 ∗ 代表雷，数字 $0−9$ 即生成后的数字。

对于第一个询问，其生成完数字后的模样见下：

	∗ 2 ∗
	1 2 1

数字之和为 $6$ 。

# 题解：前缀和 + 容斥原理

题目叫我们统计每个空格子的数字之和，那么这些数字的来源正是一个个雷。我们不妨考虑将这些数字统计到雷上，即记录一个 contribute 数组，表示 这个格子的雷给周围的空格子贡献了多少次（其实就是周围空格子的个数），在不考虑超出子矩阵范围的情况下，我们对 contribute 数组做二位前缀和，就可以很轻松地应对每次询问了。

但是，我们要考虑矩阵边缘的雷，他们不能对矩阵外面的空格子做贡献！

注意到，会产生额外贡献的雷只会位于矩阵的边缘，其中，上边缘的雷会多算上方三个格子中空格子的贡献，左边缘的雷会多算左边三个格子中空格子的贡献，下边缘和右边缘的雷同理。

因此，我们可以再记录四个数组 up , left , down , right ，分别表示有雷的格子的上方、左侧、下方、右侧产生了几次贡献，在每次询问统计答案的时候，我们用之前的 contribute 之和，减掉边缘的 up 或 left 或 down 或 right 之和。同理我们也要维护这四个数组的二维前缀和，来快速应对询问。

但是还没完！注意到左上角的格子，如果它是雷，而位于它左上角的格子是空格子，这个空格子被我们剪了两次！因此如果满足这两个条件，这个空格子的贡献得加回来一次。对于左下角、右下角、右上角的格子进行同样的处理。

这个题还有一个毒瘤的地方就是， $n, m$ 大小上限和 $n \times m$ 一样，导致我们开不出二维数组，我们只能开一个一维数组，然后每次将二维坐标换算成一维坐标操作。

补充（二维前缀和）： 设原数组为 $a[i][j]$ ，它的二维前缀和数组为 $sum[i][j]$ （即表示从 $(1, 1)$ 到 $(i, j)$ 之间的所有数之和），则预处理二维前缀和的公式为：

$sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j]$

求出 $(x_1, y_1)$ 到 $(x_2, y_2)$ 的和的公式为：

$sum[x_2][y_2] - sum[x_1 - 1][y_2] - sum[x_2][y_1 - 1] + sum[x_1 - 1][y_1 - 1]$

可以自己画个二维方阵来理解这些加加减减。

参考代码：

	#include <stdio.h>
	#include <math.h>

	const int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1};
	const int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};

	int n, m, q, map[300010], contribute[300010], up[300010], left[300010], right[300010], down[300010];

	static inline int GetCoordinate(int x, int y) // 二维坐标到一维坐标的转换
	{
	return fmax((x - 1) * m + y, 0);
	}

	static inline int GetMatPrefix(int arr[], int x1, int y1, int x2, int y2) // 利用二维前缀和求子矩阵中数的和
	{
	return arr[GetCoordinate(x2, y2)] - arr[GetCoordinate(x1 - 1, y2)] - arr[GetCoordinate(x2, y1 - 1)] + arr[GetCoordinate(x1 - 1, y1 - 1)];
	}

	int main()
	{
	// freopen("J.in", "r", stdin);
	// freopen("J.out", "w", stdout);

	scanf("%d%d%d", &n, &m, &q);

	for (int i = 1; i <= n * m; ++ i)
	scanf("%d", &map[i]);

	for (int i = 1; i <= n; ++ i)
	for (int j = 1; j <= m; ++ j)
	{
	int p = GetCoordinate(i, j);

	if (!map[p]) // 不是雷的格子我们不统计贡献
	continue;

	for (int k = 0; k < 8; ++ k)
	{
	int x = i + dx[k], y = j + dy[k];
	int q = GetCoordinate(x, y);

	if (x >= 1 && x <= n && y >= 1 && y <= m && !map[q])
	++ contribute[p];
	}

	for (int k = -1; k <= 1; ++ k) // up
	{
	int x = i - 1, y = j + k;
	int q = GetCoordinate(x, y);

	if (x >= 1 && x <= n && y >= 1 && y <= m && !map[q])
	++ up[p];
	}

	for (int k = -1; k <= 1; ++ k) // left
	{
	int x = i + k, y = j - 1;
	int q = GetCoordinate(x, y);

	if (x >= 1 && x <= n && y >= 1 && y <= m && !map[q])
	++ left[p];
	}

	for (int k = -1; k <= 1; ++ k) // right
	{
	int x = i + k, y = j + 1;
	int q = GetCoordinate(x, y);

	if (x >= 1 && x <= n && y >= 1 && y <= m && !map[q])
	++ right[p];
	}

	for (int k = -1; k <= 1; ++ k) // down
	{
	int x = i + 1, y = j + k;
	int q = GetCoordinate(x, y);

	if (x >= 1 && x <= n && y >= 1 && y <= m && !map[q])
	++ down[p];
	}
	}

	for (int i = 1; i <= n; ++ i)
	for (int j = 1; j <= m; ++ j)
	{
	contribute[GetCoordinate(i, j)] += contribute[GetCoordinate(i, j - 1)] + contribute[GetCoordinate(i - 1, j)] - contribute[GetCoordinate(i - 1, j - 1)]; // 二维前缀和累加
	up[GetCoordinate(i, j)] += up[GetCoordinate(i, j - 1)] + up[GetCoordinate(i - 1, j)] - up[GetCoordinate(i - 1, j - 1)];
	down[GetCoordinate(i, j)] += down[GetCoordinate(i, j - 1)] + down[GetCoordinate(i - 1, j)] - down[GetCoordinate(i - 1, j - 1)];
	left[GetCoordinate(i, j)] += left[GetCoordinate(i, j - 1)] + left[GetCoordinate(i - 1, j)] - left[GetCoordinate(i - 1, j - 1)];
	right[GetCoordinate(i, j)] += right[GetCoordinate(i, j - 1)] + right[GetCoordinate(i - 1, j)] - right[GetCoordinate(i - 1, j - 1)];
	}

	while (q -- )
	{
	int x1, y1, x2, y2;
	scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
	int ans = GetMatPrefix(contribute, x1, y1, x2, y2) - GetMatPrefix(up, x1, y1, x1, y2) - GetMatPrefix(left, x1, y1, x2, y1) - GetMatPrefix(down, x2, y1, x2, y2) - GetMatPrefix(right, x1, y2, x2, y2);

	if (x1 - 1 > 0 && y1 - 1 > 0 && !map[GetCoordinate(x1 - 1, y1 - 1)] && map[GetCoordinate(x1, y1)])
	++ ans; // 这是多减掉的格子，补回来

	if (x1 - 1 > 0 && y2 + 1 <= m && !map[GetCoordinate(x1 - 1, y2 + 1)] && map[GetCoordinate(x1, y2)])
	++ ans;

	if (x2 + 1 <= n && y1 - 1 > 0 && !map[GetCoordinate(x2 + 1, y1 - 1)] && map[GetCoordinate(x2, y1)])
	++ ans;

	if (x2 + 1 <= n && y2 + 1 <= m && !map[GetCoordinate(x2 + 1, y2 + 1)] && map[GetCoordinate(x2, y2)])
	++ ans;

	printf("%d\n", ans);
	}

	return 0;
	}

前缀和容斥原理