前缀和与差分专题

领地选择

（二维前缀和）

作为在虚拟世界里统帅千军万马的领袖，小 Z 认为天时、地利、人和三者是缺一不可的，所以，谨慎地选择首都的位置对于小 Z 来说是非常重要的。

首都被认为是一个占地 C×C 的正方形。小 Z 希望你寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。

第一行三个整数 N,M,CN,M,C，表示地图的宽和长以及首都的边长。

接下来 NN 行每行 MM 个整数，表示了地图上每个地块的价值。价值可能为负数。

输入数据

3 4 2
1 2 3 1
-1 9 0 2
2 0 1 1

 输出数据

1 2

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n, m, c;
	cin >> n >> m >> c;
	vector<vector<int>> a(n+1, vector<int>(m+1, 0)), g(n+1, vector<int>(m+1,0));
	for (int i=1; i<=n; i++){
		for (int j = 1; j<=m; j++){
			cin >> a[i][j];
			g[i][j] = g[i][j-1]+g[i-1][j]-g[i-1][j-1]+a[i][j];
		}
	}
	int max = -1e9, mai=0,maj=0;
	for (int i = c; i<=n; i++){
		for (int j = c; j <=m; j++){
			int ans = g[i][j]-g[i][j-c]-g[i-c][j]+g[i-c][j-c];
			if (ans > max){
				max = ans;
				mai = i-c+1;
				maj = j-c+1;
			}
		}
	}
	cout << mai << " " << maj << endl;
	return 0;
}

地毯 

（二维差分）

在 n×n 的格子上有 mm 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

第一行，两个正整数 n,mn,m。意义如题所述。

接下来 m 行，每行两个坐标 (x1,y1) 和 (x2,y2)，代表一块地毯，左上角是 (x1,y1)，右下角是 (x2,y2)。

输入数据

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

注意差分方式为下表，以5*5中的点一(1,1),点二(3,3)为例

 这里a的数组为什么要开n+2呢，因为当x2,y2为边界时得在它+1的位置-1.

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n+2, vector<int>(n+2, 0)), g(n+2, vector<int>(n+1, 0));
	for (int i = 0; i<m; i++){
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		a[x1][y1]++;
		a[x2+1][y1]--;
		a[x1][y2+1]--;
		a[x2+1][y2+1]++;
	}
	for (int i = 1; i<=n; i++){
		for (int j = 1; j<=n; j++){
			g[i][j] = g[i-1][j]+g[i][j-1]-g[i-1][j-1]+a[i][j];
			cout << g[i][j] << " \n"[j==n];
		}
	}
	
	return 0;
}