【模板】二维差分

P1061 - 【模板】二维差分 - ETOJ (eriktse.com)

#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
const int N=1e3+23;
using ll=long long;
ll a[N][N],fix[N][N],diff[N][N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

ll n,m,q;cin>>n>>m>>q;

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){
cin>>a[i][j];}}

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){
diff[i][j]=a[i][j]+a[i-1][j-1]-a[i-1][j]-a[i][j-1];}}

while(q--) {
	int x1,y1,x2,y2,x;cin>>x1>>y1>>x2>>y2>>x;
	diff[x1][y1]+=x;
	diff[x2+1][y2+1]+=x;
	diff[x1][y2+1]-=x;	
	diff[x2+1][y1]-=x;
}

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+diff[i][j];
}}

for(int i=1;i<=n;i++){

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


}