Monitor HDU - 6514（二维差分，二维前缀和）

https://vjudge.net/problem/HDU-6514#

二维差分：

// x1，y1是左上角，x2，y2是右下角
sum[x1][y1]+=d;
sum[x1][y2+1]-=d;
sum[x2+1][y1]-=d;
sum[x2+1][y2+1]+=d;

求前缀和：

 for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
            sum[i][j] = sum[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];

求一个区间的和：

ans = sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];

#include <bits/stdc++.h>

using namespace std;

void modify(int x1, int y1, int x2, int y2, int d, vector<vector<int> > & sum)
{   
    sum[x1][y1]+=d;
    sum[x1][y2+1]-=d;
    sum[x2+1][y1]-=d;
    sum[x2+1][y2+1]+=d;
}

void update(int n, int m, vector<vector<int> > & sum) {
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
            sum[i][j] = sum[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(sum[i][j] > 0) {
                sum[i][j] = 1;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            sum[i][j] = sum[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
        }
    }
}

int main()
{
    // freopen("i.txt", "r", stdin);
    int n, m;
    while(~scanf("%d%d", &n, &m)) 
    {
        vector<vector<int> > sum(n + 5, vector<int>(m + 5, 0));
        int T;
        scanf("%d", &T);
        while(T--) 
        {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            modify(x1, y1, x2, y2, 1, sum);
        }
        update(n, m,sum);
        scanf("%d", &T);
        while(T--)
        {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            if(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1] == (x2-x1+1) * (y2-y1+1)) {
                printf("YES\n");
            }
            else printf("NO\n");
        }  

    }
    return 0;
}