D.牛妹吃豆子(二维前缀和&差分数组）

题目传送门

给定矩阵：k个区间修改，给q个询问区间和。

思路：二维差分数组板子题。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
typedef long long ll;
ll a[N][N];
int main(){
    int n,m,k,q;
    scanf("%d%d%d%d",&n,&m,&k,&q);
    while(k--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        a[x1][y1]++;
        a[x1][y2+1]--;
        a[x2+1][y1]--;
        a[x2+1][y2+1]++;
    }
    for(int k=0;k<2;k++) //迭代两遍,第一遍利用差分数组求原数组,第二遍递推前缀和. 
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];//第二遍右边的a[i][j]代表数组中的数.递推后变成前缀和 
    while(q--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%lld\n",a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]);
    }
    return 0;
}