D 牛妹吃豆子

本题考查 二维差分+二维前缀和
虽然点(1,1)在左下角，(n,m)在右上角，但画图翻转一下可发现无影响

1.二维前缀和，a[i][j]求得是从(1,1)开始到(i,j)这一块矩形的总和，公式如下

For(i, 1, n) For(j, 1, m) a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];

2.(x1,y1)到(x2,y2)构成矩形数据和

k = a[x2][y2] - a[x2][y1 - 1] - a[x1][y2 - 1] + a[x1 - 1][y1 - 1];

可仿上图自己推
3.二维差分

++a[x1][y1], ++a[x2 + 1][y2 + 1], --a[x2 + 1][y1], --a[x1][y2 + 1];

4.进行完二维差分工作后，进行二维前缀和推出各点各增加或减少多少

For(i, 1, n) For(j, 1, m) a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];

5.如果原来数组元素值不全为零，则需要两个数组相加后再进行二维前缀和，否则直接进行二维前缀和即可
总代码如下

#pragma warning (disable :4996)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = cos(-1.0);
const double eps = 1e-10;
#define For(i,n,m) for(int i=n;i<=m;++i)

ll n, m, k, q;
ll x1, y1, x2, y2;
ll a[2020][2020];
int main() {
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m >> k >> q;
    while (k--) {
        cin >> x1 >> y1 >> x2 >> y2;
        ++a[x1][y1], ++a[x2 + 1][y2 + 1], --a[x2 + 1][y1], --a[x1][y2 + 1];
    }
    For(i, 1, n) For(j, 1, m) a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];
    For(i, 1, n) For(j, 1, m) a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];
    while (q--) {
        cin >> x1 >> y1 >> x2 >> y2;

        cout << a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1] << "\n";
    }
    return 0;
}