思路

前缀和 + vector

题目 n * m <= 1e7 不能定义二维数组, 考虑(1)二维vector s (2)一维数组(二维变换) s[i]
把所有监控范围内的差分数组a[i][j] +1 , 计算a[i][j]的前缀和s[i][j], 然后再将前缀和数组 >= 1的置为1(相当于监控块的面积), 然后计算s[i][j]前缀和表示(i, j) -> (1, 1)有监控的面积, 再与输入坐标所构成的矩形面积做对比, 相等即为能看到小偷, 反之, 不能

cin >> x1 >> y1 >> x2 >> y2 -> TLE

算法

1. 前缀和:(1) 一维 (2) 二维 (3) 更多…
2. vector:(1) resize() 分配空间
   (2) 表示二维以上 a[i][j]…
   (3) 更多点击

算法一

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>> s;

int n, m;

int main()
{
    while(cin >> n >> m)
    {
        s.resize(n + 10);
        for(int i = 0; i < n + 10; i ++ ) 
            s[i].resize(m + 10);

        int p;
        cin >> p;
        while(p -- )
        {
            int x1, y1, x2, y2;
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            s[x1][y1] ++ , s[x2 + 1][y1] -- , s[x1][y2 + 1] -- , s[x2 + 1][y2 + 1] ++ ;
        }
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ )   
                s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ )
                s[i][j] = min(1, s[i][j]);
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ )
                s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        int q;
        cin >> q;
        while(q -- )
        {
            int x1, y1, x2, y2;
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            if(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] == (x2 - x1 + 1) * (y2 - y1 + 1))  
                cout << "YES" << endl;
            else 
                cout << "NO" << endl;
        }   
        for(int i = 0; i < n + 10; i ++ )
            for(int j = 0; j < m + 10; j ++ )
                s[i][j] = 0;
    }
    return 0;
}

算法二

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e7 + 10;

int n, m;
int s[N]; 

int id(int x, int y)
{
    if(x == 0 || y == 0 || x > n || y > m)
        return 0;
    else 
        return (x - 1) * m + y;
}

int main()
{
    while(cin >> n >> m)
    {
        int p;
        cin >> p;
        while(p -- )
        {
            int x1, y1, x2, y2;
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            if(id(x1, y1))         s[id(x1, y1)] ++ ;
            if(id(x2 + 1, y1))     s[id(x2 + 1, y1)] -- ;
            if(id(x1, y2 + 1))     s[id(x1, y2 + 1)] -- ;
            if(id(x2 + 1, y2 + 1)) s[id(x2 + 1, y2 + 1)] ++ ;
        }
        for(int i = 1; i <= n; i ++ )       
            for(int j = 1; j <= m; j ++ )
                s[id(i, j)] += s[id(i - 1, j)] + s[id(i, j - 1)] - s[id(i - 1, j - 1)];
        for(int i = 1; i <= n; i ++ )   
            for(int j = 1; j <= m; j ++ )
                s[id(i, j)] = min(1, s[id(i, j)]);
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ )
                s[id(i, j)] += s[id(i - 1, j)] + s[id(i, j - 1)] - s[id(i - 1, j - 1)];
        int q;
        cin >> q;
        while(q -- )
        {
            int x1, y1, x2, y2;
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            if(s[id(x2, y2)] - s[id(x1 - 1, y2)] - s[id(x2, y1 - 1)] + s[id(x1 - 1, y1 - 1)] == (x2 - x1 + 1) * (y2 - y1 + 1))
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
        memset(s, 0, sizeof s);
    }
    return 0;
}