组队训练14补题

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[x11,y21]-c;b[x21,y1]-c;b[x21,y21]c;​接下来我们进入正题这题要求我们求出一块画布上的每个坐标点可以画出多少个整点正方形。我们不妨对构建正方形的向量a,b)进行枚举求出构建出的正方形对哪些点有影响。构建出的正方形可以在画布上平移它对画布上的点的影响范围可以构成一个矩形。我们只要用二维差分将它影响的范围进行更新最后求前缀和还原就行了。下面贴上代码#includebits/stdc.husingnamespacestd;#defineintlonglongsignedmain(){intn,m;cinnm;n,m;vectorvectorintg(n1,vectorint(m1));for(inta0;amin(n,m);a){for(intb1;bamin(n,m);b){autowork[](intl,intu){intrm-a-bl,dn-a-bu;//求出上下左右边界然后更新差分数组g[u][l];g[u][r]--;g[d][l]--;g[d][r];};work(0,a);work(b,0);work(a,ab);work(ab,b);}}for(inti1;in;i){for(intj0;jm;j){g[i][j]g[i-1][j];}}for(inti0;in;i){for(intj1;jm;j){g[i][j]g[i][j-1];}}for(inti0;in;i){for(intj0;jm;j){if(j!0)cout ;coutg[i][j];}cout\n;}}