传送门1
传送门2
一维请出门右转。
二维前缀和
d[i][j]表示从 (1,1) 点到 (i,j) 点的和。
很显然：
求d数组：d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+a[i][j]
求(a,b)到(c,d)的和：d[c][d]-d[a-1][d]-d[c][b-1]+a[i-1][b-1]
二维差分
本质是二维前缀和的逆运算。
不是很好解释具体含义。
求原数组：d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+d[i][j]
对区间(a,b)到(c,d)加v：d[a][b]+=v,d[a][d+1]-=v,d[c+1][b]-=v,d[c+1][d+1]+=v
AC代码
领地选择
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e3+5;
int n,m,a[maxn][maxn],d[maxn][maxn],c,ans=-1e9,ansx,ansy;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>c;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+a[i][j];
}
}
for(int i=c;i<=n;i++){
for(int j=c;j<=m;j++){
int now=d[i][j]-d[i-c][j]-d[i][j-c]+d[i-c][j-c];
if(now>ans){
ans=now;
ansx=i-c+1,ansy=j-c+1;
}
}
}
cout<<ansx<<" "<<ansy;
return 0;
}
地毯
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
const int maxn=1005;
int n,m,d[maxn][maxn];
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++){
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
d[x1][y1]++;
d[x2+1][y1]--;
d[x1][y2+1]--;
d[x2+1][y2+1]++;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+d[i][j];
cout<<d[i][j]<<" ";
}
cout<<endl;
}
return 0;
}