• HDU 6514 - Monitor(前缀和与差分)


    Problem Description
    Xiaoteng has a large area of land for growing crops, and the land can be seen as a rectangle of n × m n×m n×m.

    But recently Xiaoteng found that his crops were often stolen by a group of people, so he decided to install some monitors to find all the people and then negotiate with them.

    However, Xiao Teng bought bad monitors, each monitor can only monitor the crops inside a rectangle. There are p p p monitors installed by Xiaoteng, and the rectangle monitored by each monitor is known.

    Xiao Teng guess that the thieves would also steal q q q times of crops. he also guessed the range they were going to steal, which was also a rectangle. Xiao Teng wants to know if his monitors can see all the thieves at a time.

    Input
    There are mutiple test cases.

    Each case starts with a line containing two integers n , m ( 1 ≤ n , 1 ≤ m , n × m ≤ 1 0 7 ) n,m(1≤n,1≤m,n×m≤10^7) n,m(1n,1m,n×m107) which represent the area of the land.

    And the secend line contain a integer p ( 1 ≤ p ≤ 1 0 6 ) p(1≤p≤10^6) p(1p106) which represent the number of the monitor Xiaoteng has installed. This is followed by p lines each describing a rectangle. Each of these lines contains four intergers x 1 , y 1 , x 2 x_1,y_1,x_2 x1,y1,x2 and y 2 ( 1 ≤ x 1 ≤ x 2 ≤ n , 1 ≤ y 1 ≤ y 2 ≤ m ) y_2(1≤x_1≤x_2≤n,1≤y_1≤y_2≤m) y2(1x1x2n,1y1y2m) ,meaning the lower left corner and upper right corner of the rectangle.

    Next line contain a integer q ( 1 ≤ q ≤ 1 0 6 ) q(1≤q≤10^6) q(1q106) which represent the number of times that thieves will steal the crops.This is followed by q lines each describing a rectangle. Each of these lines contains four intergers x 1 , y 1 , x 2 x1,y1,x2 x1,y1,x2 and y 2 ( 1 ≤ x 1 ≤ x 2 ≤ n , 1 ≤ y 1 ≤ y 2 ≤ m ) y_2(1≤x_1≤x_2≤n,1≤y_1≤y_2≤m) y2(1x1x2n,1y1y2m),meaning the lower left corner and upper right corner of the rectangle.

    Output
    For each case you should print q lines.

    Each line containing YES or NO mean the all thieves whether can be seen.

    Sample Input

    6 6
    3
    2 2 4 4
    3 3 5 6
    5 1 6 2
    2
    3 2 5 4
    1 5 6 5
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    Sample Output

    YES
    NO
    
    • 1
    • 2

    Hint
    In the picture,the red solid rectangles mean the monitor Xiaoteng installed, and the blue dotted rectangles mean the area will be stolen.

    在这里插入图片描述


    基本思路就是先利用差分给每个装了监控的区域做一个标记,然后计算前缀和,如果某个点能被监控到,则在上面放上1这个数,如果该区域能被完全覆盖,则该区域的面积(x2 - x1 + 1) * (y2 - y1 + 1)(题目保证了 x 2 > x 1 x_2 > x_1 x2>x1以及 y 2 > y 1 y_2 > y_1 y2>y1)应该要等于这一段区域的前缀和,即1的个数。

    要注意的是*:

    • 由于题目所给的数据m*n < 1 0 7 10^7 107,开二维数组[1e7][1e7]显然不可能,所以放到一维数组中存储,让每个坐标 ( x , y ) (x,y) (x,y)唯一地映射到一维数组中的某个位置。
    • 由于某个点可能会被监控反复地覆盖到,所以为了去重,在第一遍前缀和处理之后,再对每个点上存的数> 0的情况平滑一下,即置为1;然后在此平滑处理的基础上,进行第二遍前缀和,这时的前缀和才是可以用于结果比较的。

    C++代码

    #include 
    #include 
    using namespace std;
    
    const int N = 1e7 + 10;
    
    int n, m, p, q;
    int a[N];         //存图,考虑到二维空间肯定是不够,所以需要压缩成一维
    
    int addr(int x, int y){     //(x,y) -> 一个int型的地址
        if(x == 0 || y == 0 || x > n || y > m)      return 0;       //****处理一下边界****
        
        return (x - 1) * m + y;     //自己设置的映射函数
    }
    
    void insert(int x1, int y1, int x2, int y2){        //差分
        a[addr(x1, y1)] += 1;
        a[addr(x1, y2 + 1)] -= 1;
        a[addr(x2 + 1, y1)] -= 1;
        a[addr(x2 + 1, y2 + 1)] += 1;     
    }
    
    int main(){
        
        while(~scanf("%d%d", &n, &m)){
            int x1, y1, x2, y2;
            memset(a, 0, sizeof a);
            
            scanf("%d", &p);
            while(p --){
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                insert(x1, y1, x2, y2);
            }
            
            //先预处理一遍前缀和,被monito到重复的区域也考虑在内
            for(int i = 1;i <= n;i ++)
                for(int j = 1;j <= m;j ++)
                    a[addr(i, j)] = a[addr(i - 1, j)] + a[addr(i, j - 1)] - a[addr(i - 1, j - 1)] + a[addr(i, j)];
            
            //去掉重复区域,将所有被覆盖(> 0)到的区域都置1    
            for(int i = 1;i <= n;i ++)
                for(int j = 1;j <= m;j ++)
                    if(a[addr(i, j)] > 0)       a[addr(i, j)] = 1;
            
            //再处理前缀和
            for(int i = 1;i <= n;i ++)
                for(int j = 1;j <= m;j ++)
                    a[addr(i, j)] = a[addr(i - 1, j)] + a[addr(i, j - 1)] - a[addr(i - 1, j - 1)] + a[addr(i, j)];
            
            
            scanf("%d", &q);
            while(q --){
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                //区域面积等于区域1的和则表明被全覆盖
                int s = a[addr(x2, y2)] - a[addr(x1 - 1, y2)] - a[addr(x2, y1 - 1)] + a[addr(x1 - 1, y1 - 1)];
                
                if(s == (x2 - x1 + 1) * (y2 - y1 + 1))      cout << "YES" << endl;
                else        cout << "NO" << endl;
            }
        }
        
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
  • 相关阅读:
    微服务nacos实战入门
    cannot access ‘/docker-entrypoint-initdb.d/‘: Operation not permitted
    【干货】Vue2.x 组件通信方式详解,这篇讲全了
    哪些字符串会被FastJson解析为null呢
    数据结构概述
    python中class使用总结
    24深圳杯数学建模挑战赛A题6页初步思路+参考论文+保姆级答疑!!!
    1.5-07:奥运奖牌计数
    mysql 配置主从复制 及 Slave_SQL_Running = no问题排查
    【Spring系列】- Bean生命周期底层原理
  • 原文地址:https://blog.csdn.net/weixin_53024141/article/details/127674426