企业官网建设流程全解析

A - 整点正方形计数2

引入：
本题需要用到二维差分。假设b数组是a数组的差分数组，那反过来a就是b的前缀和数组矩阵。

我们去构造差分数组： b[i][j]

使得a数组中a[i][j]是b数组左上角(1,1)到右下角(i,j)所包围矩形元素的和。

如果我们要对a中以坐标（x1,y1）为左上角，（x2,y2）为右下角的矩形加一个数。在差分数组b中，进行以下操作：

b[x1,y1]+=c;

b[x1+1,y2+1]-=c;

b[x2+1,y1]-=c;

b[x2+1,y2+1]+=c;

​
接下来我们进入正题
这题要求我们求出一块画布上的每个坐标点可以画出多少个整点正方形。
我们不妨对构建正方形的向量（a,b)进行枚举，求出构建出的正方形对哪些点有影响。构建出的正方形可以在画布上平移，它对画布上的点的影响范围可以构成一个矩形。我们只要用二维差分将它影响的范围进行更新，最后求前缀和还原就行了。
下面贴上代码：

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongsignedmain(){intn,m;cin>>n>>m;n++,m++;vector<vector<int>>g(n+1,vector<int>(m+1));for(inta=0;a<min(n,m);a++){for(intb=1;b+a<min(n,m);b++){autowork=[&](intl,intu){intr=m-a-b+l,d=n-a-b+u;//求出上下左右边界，然后更新差分数组g[u][l]++;g[u][r]--;g[d][l]--;g[d][r]++;};work(0,a);work(b,0);work(a,a+b);work(a+b,b);}}for(inti=1;i<n;i++){for(intj=0;j<m;j++){g[i][j]+=g[i-1][j];}}for(inti=0;i<n;i++){for(intj=1;j<m;j++){g[i][j]+=g[i][j-1];}}for(inti=0;i<n;i++){for(intj=0;j<m;j++){if(j!=0)cout<<' ';cout<<g[i][j];}cout<<'\n';}}