二维差分以及二维前缀和

妖狐艹你老母 2022-01-07 23:43 324阅读 0赞

暑假补课开始了呀，第一天就学了这个东东，以及有道第一次见了不会写，这次补出来了的题

题目：Monitor

因为是学校VJ上挂的题啦，所以我给链接没法访问的，你们可以直接百度这题就ok了

题意就是给定一个n\*m（n\*m<1e7)的二维空间

给n1次x1,y1,x2,y2表示被监控的区域的左下右上顶点坐标（可能会有覆盖区域）

给n2次x1,y1,x2,y2表示询问该区域是否被完全监控，是输出YES，否输出NO

样例

6 6

2 2 4 4

3 3 5 6

5 1 6 2

3 2 5 4

1 5 6 5

输出

YES

解析，就是二维差分数组进行区间修改，然后二维差分数组的前缀和得到原数组，再修改下原数组，有值为1，无为0

然后对原数组再搞一次前缀和，求查询区间的面积如果和原数组二维前缀和相等则说明全覆盖

AC代码还有点注释

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
       int n,m;
       ios::sync_with_stdio(false);
       while(cin>>n>>m){
       int ditu[n+10][m+10];///平时老师是不让这么开数组的
       int a1[n+10][m+10];///所以你也可以用指针
       int a[n+10][m+10];
       for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
           ditu[i][j]=a1[i][j]=a[i][j]=0;///初始化，因为这题是多组
       int zs;
       cin>>zs;
       while(zs--)
       {
           int x1,x2,y1,y2;
           cin>>x1>>y1>>x2>>y2;
           ditu[x1][y1]++;
           ditu[x2+1][y1]--;
           ditu[x1][y2+1]--;
           ditu[x2+1][y2+1]++;///二维差分数组O1复杂度区间修改
       }
       for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        a1[i][j]=a1[i-1][j]+a1[i][j-1]-a1[i-1][j-1]+ditu[i][j];///得原数组
       for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a1[i][j]!=0)
            a1[i][j]=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]+a1[i][j];///得原数组前缀和
       cin>>zs;
       while(zs--)
       {
           int x1,x2,y1,y2;
           cin>>x1>>y1>>x2>>y2;
           if((a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1])==((x2-x1+1)*(y2-y1+1)))
            cout<<"YES"<<endl;///按条件判断
           else
            cout<<"NO"<<endl;
       }
       }
    }