前置芝士

二维差分数组

\(1≤q≤100000,1≤n,m≤10^3,1≤x1≤x2≤n,1≤y1≤y2≤m,1≤a_{i,j},c≤10^5\)

void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    vector<vector<ll>> a(n+1,vector<ll>(m+1,0));
    vector<vector<ll>> b(n+2,vector<ll>(m+2,0));
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++) cin>>a[i][j];
    while(q--){
    	int x0,y0,x1,y1,c;
    	cin>>x0>>y0>>x1>>y1>>c;
        // cout<<x0<<y0<<x1<<y1<<c<<endl;
	//下标从1开始
    	b[x0][y0]+=c;
    	b[x0][y1+1]-=c;
    	b[x1+1][y0]-=c;
    	b[x1+1][y1+1]+=c;
    }
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		b[i][j]+=b[i][j-1]+b[i-1][j]-b[i-1][j-1];
    		cout<<b[i][j]+a[i][j]<<" ";
    	}
    	cout<<endl;
    }
}