领地选择
（二维前缀和）
作为在虚拟世界里统帅千军万马的领袖，小 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)为例
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | 1 | -1 | ||||
| 2 | ||||||
| 3 | ||||||
| 4 | -1 | 1 | ||||
| 5 | ||||||
这里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;
}