牛客小白月赛24 D.牛妹吃豆子

考点:二维差分，前缀和。
这题题意很明确，做法也很明确，先对前k个操作差分，再进行二维前缀和，直接O(1)查询就行了。

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 10000;
const int N = 5e6 + 10;
ll a[2010][2010];
int main()
{
#ifdef LOCAL
    freopen("E:/input.txt", "r", stdin);
#endif
    int n, m, k, q;
    cin >> n >> m >> k >> q;
    for (int i = 1; i <= k; i++)
    {
        int x1, x2, y1, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        int c = 1;
        a[x1][y1] += c;
        a[x2 + 1][y1] -= c;
        a[x1][y2 + 1] -= c;
        a[x2 + 1][y2 + 1] += c;
    }
    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];
        }
    }
    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];
        }
    }
    while (q--) 
    {
        int x1, x2, y1, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        ll num = a[x2][y2] + a[x1 - 1][y1 - 1] - a[x1 - 1][y2] - a[x2][y1 - 1];
        printf("%lld\n", num);
    }
    return 0;
}