本文共 2943 字，大约阅读时间需要 9 分钟。

题目大意

给出一个$n\ast m$的麦田（左下角为$(1,1)，$右上角$(n,m)$），其中有$p$个矩形区域安装了监控，接下来有$q$个贼想偷某个矩形范围内的庄稼，问监控能否拍到贼。

解题思路

这时一道考验二维差分+二维前缀和的一道非常好的题目。

首先我们需要将有监控的区域都置为$1$，也就是每个监控区域的所有元素都加一，这时不难想到二维差分，有的元素可能被多个监控重复覆盖，那么差分矩阵还原时需要将大于$1$的元素置为$1$。然后对还原的矩阵求前缀和，只需要看贼偷东西的矩阵的元素和是否为矩阵面积。

题目有两大坑点：

• 题目给的坐标是左下角为$(1,1)，$右上角$(n,m)$的矩阵，但是计算机存储的矩阵是左上角为$(1,1)，$右下角$(n,m)$。要么坐标转化一下，要么将矩阵颠倒一下。

• 矩阵的范围是$n\ast m\le 1e7$，无法通过数组存，要么使用$vector$套$vector$，要么就使用一维数组模拟二维数组，将下标转化一下。

一开始写了好久的一维数组一直挂，不知道哪里错了改了二维动态数组就过了，离谱

//// Created by Happig on 2020/10/29//#include <bits/stdc++.h>#include <unordered_map>#include <unordered_set>using namespace std;#define fi first#define se second#define pb push_back#define ins insert#define Vector Point#define ENDL "\n"#define lowbit(x) (x&(-x))#define mkp(x, y) make_pair(x,y)#define mem(a, x) memset(a,x,sizeof a);typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair<int, int> pii;typedef pair<ll, ll> pll;typedef pair<double, double> pdd;const double eps = 1e-8;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double dinf = 1e300;const ll INF = 1e18;const int Mod = 1e9 + 7;const int maxn = 1e7 + 10;void add(vector<vector<int>> &d, int i, int j, int x, int y, int val) {       d[i][j] += val, d[x + 1][y + 1] += val;    d[i][y + 1] -= val, d[x + 1][j] -= val;}int getSum(vector<vector<int>> &d, int i, int j, int x, int y) {       return d[x][y] - d[i - 1][y] - d[x][j - 1] + d[i - 1][j - 1];}int main() {       //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, m, p, q;    int lx, ly, rx, ry;    while (cin >> n >> m) {           vector<vector<int> > d(n + 2, vector<int>(m + 2));        cin >> p;        while (p--) {               cin >> lx >> ly >> rx >> ry;            lx = n + 1 - lx, rx = n + 1 - rx;            swap(lx, rx);            add(d, lx, ly, rx, ry, 1);        }        for (int i = 1; i <= n; i++) {               for (int j = 1; j <= m; j++) {                   d[i][j] = d[i][j] + d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];            }        }        for (int i = 1; i <= n; i++) {               for (int j = 1; j <= m; j++) {                   if (d[i][j]) d[i][j] = 1;            }        }        for (int i = 1; i <= n; i++) {               for (int j = 1; j <= m; j++) {                   d[i][j] = d[i][j] + d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];            }        }        cin >> q;        while (q--) {               cin >> lx >> ly >> rx >> ry;            lx = n + 1 - lx, rx = n + 1 - rx;            swap(lx, rx);            int ans = getSum(d, lx, ly, rx, ry);            if (ans == (rx - lx + 1) * (ry - ly + 1)) cout << "YES" << endl;            else cout << "NO" << endl;        }    }    return 0;}