题解

传送门 HDU 6514 Monitor

题解

对每个监视器所覆盖的矩形区域进行二维差分，取前缀和所得到的 s u m i , j sum_{i,j} sumi,j​ 代表点 ( i , j ) (i,j) (i,j) 被覆盖的监视器数量，因为只考虑点是否被覆盖，那么取 s u m i , j = s i g n ( s u m i , j ) sum_{i,j}=sign(sum_{i,j}) sumi,j​=sign(sumi,j​)。为了 O ( 1 ) O(1) O(1) 求解偷盗者覆盖矩形区域是否都覆盖了监视器，对 s u m i , j sum_{i,j} sumi,j​ 取前缀和得到 s u m i , j ′ sum^{\prime}_{i,j} sumi,j′​，代表 [ 1 , i ] × [ 1 , j ] [1,i]\times [1,j] [1,i]×[1,j] 区内域覆盖了监视器的点数。判断区域内覆盖了监视器的点数是否等于区域内总点数即可。总时间复杂度 O ( N M ) O(NM) O(NM)。

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;
int N, M, P, Q;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    while (cin >> N >> M)
    {
        mat a(N + 2, vec(M + 2));
        cin >> P;
        for (int i = 0; i < P; ++i)
        {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            ++a[x1][y1], --a[x1][y2 + 1], --a[x2 + 1][y1], ++a[x2 + 1][y2 + 1];
        }
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= M; ++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] > 0) + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        cin >> Q;
        for (int i = 0; i < Q; ++i)
        {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            int tar = (y2 - y1 + 1) * (x2 - x1 + 1);
            int sum = a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1];
            cout << (sum == tar ? "YES" : "NO") << '\n';
        }
    }
    return 0;
}