二维前缀和+差分 HDU6514 Monitor

题目大意：给你个n×m的区域，每个区域被选中标记为1，没被选中标记为0，然后给一些标记的区域，查询若干个区域问是否有0的

一道二维前缀和的题目，想通没什么难度

代码如下

#include <bits/stdc++.h>
using namespace std;

#define IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define fin freopen("in.txt", "r", stdin)
#define fout freopen("out.txt", "w", stdout)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int maxn = 1e7 + 10;
const int INF = 0x3f3f3f3f;
const double eps = 1e-5;

int n, m, p, q;
int a[maxn];

int getid(int i, int j)
{
    if (i == 0 || j == 0 || i > n || j > m)
        return 0;
    return (i - 1) * m + j;
}

void add(int i, int j, int v)
{
    int id = getid(i, j);
    if (!id)
        return;
    a[id] += v;
}

int main(void)
{
    IO;
    while (~scanf("%d%d", &n, &m)) {
        memset(a, 0, sizeof(a));
        int x1, y1, x2, y2;
        scanf("%d", &p);
        for (int i = 0; i < p; i++) {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            add(x1, y1, 1);
            add(x2 + 1, y2 + 1, 1);
            add(x1, y2 + 1, -1);
            add(x2 + 1, y1, -1);
        }

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

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (a[getid(i,j)] > 0)
                    a[getid(i, j)] = 1;

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

        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            int ans = a[getid(x2, y2)] - a[getid(x1 - 1, y2)] - a[getid(x2, y1 - 1)] + a[getid(x1 - 1, y1 - 1)];
            if (ans == (x2 - x1 + 1) * (y2 - y1 + 1))
                puts("YES");
            else
                puts("NO");
        }
    }

    return 0;
}

评论