题目描述

差分方程：
a[i][j]=b[i][j]+a[i][j-1]+a[i-1][j]-a[i-1][j-1];
b[i][j]=a[i][j]-a[i][j-1]-a[i-1][j]+a[i-1][j-1];
当希望在[x1,y1],[x2,y2]区间内所有元素增加c
应该让b[x1][y1]+=c;这会导致a[x1][y1,…]，a[x1…][y1]元素增加c，进而导致a[x1..][y1..]都增加c；
因此，需要在b[x1][y2+1],a[x2+1][y1]减去c。
这样的话，其它部分都不会增加c了。
但由于：a[x2+1][y2+1]=b[x2+1][y2+1]+a[x2+1][y2]+a[x2][y2+1]-a[x2][y2];
其中，a[x2+1][y2]、a[x2][y2+1]元素值不变
但a[x2][y2]已经增加了c，所以，若想a[x2+1][y2+1]不受影响，就必须让b[x2+1][y2+1]增加c。

include[HTML_REMOVED]

using namespace std;

const int N=1010;
int a[N][N],b[N][N];

int main(){
int n,m,q;
cin>>n>>m>>q;

for(int i=0;i<=n;i++)   a[i][0]=0;
for(int i=0;i<=m;i++)   a[0][i]=0;

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        scanf("%d",&a[i][j]);

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        b[i][j]=a[i][j]-a[i][j-1]-a[i-1][j]+a[i-1][j-1];

int x1,y1,x2,y2,c;
while(q--){

    scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
    b[x1][y1]+=c;
    b[x2+1][y2+1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
}

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        a[i][j]=b[i][j]+a[i][j-1]+a[i-1][j]-a[i-1][j-1];

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)
        printf("%d ",a[i][j]);
    printf("\n");
}

}

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla