[C++]洛谷 地毯 暴力及二维差分详解

[原题]

[输入样例]

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

[输出样例]

0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

[解题思路]

题目给出一个n*n的方阵，现铺上m个地毯，被地毯覆盖的所有区域值++，最终要求打印每一格的值。

最简单粗暴的做法肯定是根据题目给出的每一个地毯范围对数组进行遍历增值，最终打印，由于这种思路比较常规，这里就不多赘述，直接上代码：

#include
#include
using namespace std;

int main()
{
	//读取数据及初始化
	int n, m;
	cin >> n >> m;
	vector> grid(n, vector(n, 0));
	int s_x, s_y, d_x, d_y;
	while (m--)
	{
		cin >> s_x >> s_y >> d_x >> d_y;

		//对每一个地毯遍历增值
		for (int i = s_x - 1; i <= d_x - 1; i++)
		{
			for (int j = s_y - 1; j <= d_y - 1; j++)
			{
				grid[i][j]++;
			}
		}
	}

	//打印
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << grid[i][j];

			//去行末空格
			if (j != n - 1)
				cout << ' ';
		}

		//去末尾回车
		if (i != n - 1)
			cout << endl;
	}
	return 0;
}

不难发现，这种解法的时间复杂度达到了o(n^3)，我们需要寻找更加优化的方法。

知识链接：

一维前缀和：路径总和|||

二维前缀和：激光炸弹

接下来就是今天的重点内容了。首先，我们需要搞清楚差分到底是什么。我们先来看一种比较普遍的定义：差分是前缀和的逆运算。怎么理解这个定义呢？别急，我们先来看个例子：

现在，我们有一个长度为n的数组，如下图所示。

接着，我们需要进行这样一个操作：

①对arr[2]到arr[7]的每一项加上1，如下图。

接下来，我们再执行下一个操作：

②对arr[1]到arr[5]的每一项再加上1，如下图。

对于上面这两步，我们可以直接遍历对应的项并进行增值，我相信这两步对于大部分人来说都非常简单。但是，假如我们每次需要增值的项非常多，需要执行的步数也非常多（假定一共执行m次），如下图。

显然，对于这种情况，我们的时间复杂度接近于o(mn)，这显然有些过于庞大了。为了解决这一类问题，我们可以引入一个差分数组cf。

既然说差分是前缀和的逆运算，那么我们肯定需要一个办法，使得cf[i]的前缀和即为arr[i]的值。对于操作①和②，我们分别可以得到如下的cf数组：

不难发现，arr的每一项即为对cf求前缀和的值，而每次给出一个增值范围[a,b]后，我们只需要对cf进行两步操作：

（1）cf[a]++ ;

（2）cf[b+1]--;

接下来，为了更好地理解差分，我把差分数组比作原数组的台阶。现在，我们作出arr[i]关于i的图像。

不难看出，在每个arr数组数值变化的节点处，cf充当了一个个上升（cf>0）或下降（cf<0）的台阶，其数值反映了arr变化的大小。因此，我们可以认为，差分数组直接反映了原数组项与项之间的差值，也间接反映了随着项数i的不断增大，原数组的变化趋势。

对于一个二维数组grid[m][n]，假如我们在坐标(i0,j0)处差分数组值加上1，我们又知道对于任意grid[i][j]的值，都是对cf[i][j]求前缀和所得，因此所有前缀和包含(i0,j0)的点都会同步加上1，即红色区域的部分；同理，当cf[i0][j0]减去1，该部分的值都会同步减去1。

搞清楚了这一点，我们就可以回到我们的题目了。如果我们需要使(s_x,s_y)到(d_x,d_y)这两点之间的所有值增加1，我们需要怎么办呢？相信你如果能吃透二维前缀和的运行过程，那这一步也不难理解。

下面，我将用红色表示每一步因为cf改变而同步变化的grid区域（其中，数字代表对应位置cf数组增减值的情况，红色代表增值区域，绿色代表减值区域，灰色代表值与原始值相同的区域）。

（1）cf[s_x][s_y]++;

（2）cf[s_x][d_y+1]--;

（3）cf[d_x+1][s_y]--;

（4）cf[d_x+1][d_y+1]++;

这样，我们就完成了二维差分的赋值操作。接下来，我们来看一下这道题差分法的代码（注意越界判断）：

#include
#include
using namespace std;

//对每一组范围进行差分赋值
inline void Setcf(const int s_x, const int s_y, const int d_x, const int d_y, vector>& cf)
{
	cf[s_x][s_y]++;
	//注意此处需要进行越界判断
	if (d_y + 1 < cf.size())
		cf[s_x][d_y + 1]--;
	if (d_x + 1 < cf.size())
		cf[d_x + 1][s_y]--;
	if (d_y + 1 < cf.size() && d_x + 1 < cf.size())
		cf[d_x + 1][d_y + 1]++;
}

int main()
{
	//读取数值及初始化数组
	int n, m;
	cin >> n >> m;
	vector> grid(n, vector(n, 0));
	vector> cf(n, vector(n, 0));
	while (m--)
	{
		int s_x, s_y, d_x, d_y;
		cin >> s_x >> s_y >> d_x >> d_y;
		Setcf(s_x - 1, s_y - 1, d_x - 1, d_y - 1, cf);
	}

	//遍历
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			//根据前缀和计算法则求出每个grid的值
			grid[i][j] = (i > 0 ? grid[i - 1][j] : 0) + (j > 0 ? grid[i][j - 1] : 0) - (i > 0 && j > 0 ? grid[i - 1][j - 1] : 0) + cf[i][j];

			//打印grid[i][j]
			cout << grid[i][j];

			//去行末空格
			if (j != n - 1)
				cout << ' ';
		}
		//去末尾回车
		if (i != n - 1)
			cout << endl;
	}
	return 0;
}

可以看出，通过这种算法，整个程序的时间复杂度被压缩到了o(n^2)。