2019中山大学程序设计竞赛-Monitor

题目地址

题目大意：给你一个n*m的矩形，在这个矩形内告诉你p个矩形(左下角和右上角坐标),问你q个问题，每次也是给你一个矩形（左下角和右上角坐标)，问你每个矩形是否可以被开始给的p个矩形完全覆盖。

思路：n*m范围是1e7，无法开二维数组，二维坐标可以转化为(n-1)*m+m，用一维数组来记录每个坐标的前缀和(即为这个点与0，0点组成矩形的面积),先通过二维差分，将前缀和记录一边。因为有覆盖的情况，所以将前缀和大于0的初始化为1，在来一遍前缀和，处理好之后就可以O(1)的时间算出每个矩形是否可以覆盖。

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e7+;

int sum[maxn];

int d[maxn];

int n,m;

int fun(int x,int y)

{

    int t=m*(y-)+x;

    if(t>=&&t<=(n*m))

        return t;

    else

        return ;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    cin>>n>>m;

    int p;

    cin>>p;

    for(int i=; i<=p; i++)

    {

        int x1,y1,x2,y2;

        cin>>y1>>x1>>y2>>x2;

        d[fun(x1,y1)]+=;

        d[fun(x2+,y2+)]+=;

        d[fun(x1,y2+)]-=;

        d[fun(x2+,y1)]-=;

    }

    for(int j=; j<=n; j++)

        for(int i=; i<=m; i++)

        {

            sum[fun(i,j)]=sum[fun(i,j-)]+sum[fun(i-,j)]-sum[fun(i-,j-)]+d[fun(i,j)];

        }

    for(int i=; i<=n*m; i++)

    {

        if(sum[i]!=)

            sum[i]=;

    }

//    for(int j=n; j>=1; j--)

//    {

//        for(int i=1; i<=m; i++)

//        {

//            if(sum[fun(i,j)]!=0)

//                printf("%d ",sum[fun(i,j)]);

//            else

//                printf("0 ");

//        }

//        printf("\n");

//    }

    for(int j=; j<=n; j++)

        for(int i=; i<=m; i++)

        {

            sum[fun(i,j)]+=sum[fun(i,j-)]+sum[fun(i-,j)]-sum[fun(i-,j-)];

        }

    int q;

    cin>>q;

    for(int i=; i<=q; i++)

    {

        int x1,y1,x2,y2;

        cin>>y1>>x1>>y2>>x2;

        int ans=sum[fun(x2,y2)]-sum[fun(x2,y1-)]-sum[fun(x1-,y2)]+sum[fun(x1-,y1-)];

        if(ans==((x2-x1+)*(y2-y1+)))

            cout<<"YES"<<endl;

        else

            cout<<"NO"<<endl;

    }

}