无人机航拍题解

冷月葬T魂 · 2021-08-12 11:51:17 · 题解

首先可以发现 n,m 较小，故考虑将无人机能覆盖的所有格子记录在一个二维数组 a 中。
具体来说，将每个无人机覆盖的范围 (x_1,y_1,x_2,y_1) 分解为两个“事件”：“开始覆盖”(x_1,y_1,y_2,1) 和 “结束覆盖”(x_2+1,y_1,y_2,-1)。然后将所有事件按 x 排序，用扫描线算法，维护一个树状数组 T，记录当前 x 一行（或列，看你怎么理解坐标 (x,y)）中哪些方格被覆盖，依次处理每个事件，由于 x 变化的总数为 n，故这一步的时间复杂度为 O(nm \log m)。
然后预处理出二维数组 a 的二维前缀和，对于每个询问，判断 a 中对应子矩阵的元素和是否等于询问的总面积即可（这等价于 a 中对应子矩阵的每个元素都是 1，注意 a 中存储的是格子是否被覆盖而不是覆盖多少次）。

代码如下：

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,v) memset(a,v,sizeof(a))
//#define int long long
using namespace std;

const int N=3e3+5,M=2e6+5;

class FTree{
    int n,c[N*4];
    int lowbit(int x)
    {
        return x&(-x);
    }
public:
    void init(int _n)
    {
        n=_n;
        clr(c,0);
    }
    void poke(int p,int x)
    {
        while(p<=n){
            c[p]+=x;
            p+=lowbit(p);
        }
    }
    int peek(int p)
    {
        int res=0;
        while(p){
            res+=c[p];
            p-=lowbit(p);
        }
        return res;
    }
};

struct cpdd{
    int x,y1,y2,type;
    bool operator< (const cpdd& cp) const
    {
        return x<cp.x;
    }
}cp[M];

int n,m,s,a[N][N],sum[N][N];
FTree T;

int area(int x1,int y1,int x2,int y2)
{
    return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}

inline int read()
{
    register char Charlie;
    while((Charlie=getchar())<'0'||Charlie>'9') ;
    register int Vinnie=Charlie-'0';
    while((Charlie=getchar())>='0'&&Charlie<='9') Vinnie=(Vinnie<<3)+(Vinnie<<1)+Charlie-'0';
    return Vinnie;
}

signed main()
{
//  ios::sync_with_stdio(false);
//  cin.tie(0);
//  cout.tie(0);

//  cin>>n>>m;
    n=read();
    m=read();

//  cin>>s;
    s=read();
    For(i,1,s){
        int x1,y1,x2,y2;
//      cin>>x1>>y1>>x2>>y2;
        x1=read();
        y1=read();
        x2=read();
        y2=read();
        cp[i*2-1]=(cpdd){x1,y1,y2,1};
        cp[i*2]=(cpdd){x2+1,y1,y2,-1};
    }

    sort(cp+1,cp+1+s*2);

    int cur=1;

    T.init(m+1);

    For(i,1,s*2){
        while(cur<cp[i].x){
            For(j,1,m){
                a[cur][j] = T.peek(j)>0 ? 1 : 0;
            }
            cur++;
        }
        if(cp[i].type==1){
            T.poke(cp[i].y1,1);
            T.poke(cp[i].y2+1,-1);
        }
        else{
            T.poke(cp[i].y1,-1);
            T.poke(cp[i].y2+1,1);
        }
    }

    while(cur<=n){
        For(j,1,m){
            a[cur][j] = T.peek(j)>0 ? 1 : 0;
        }
        cur++;
    }

//  For(i,1,n){
//      For(j,1,m){
//          if(a[i][j]) cout<<'#';
//          else cout<<'.';
//      }
//      cout<<endl;
//  }
//  cout<<endl;

    For(i,1,n){
        For(j,1,m){
            sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];
        }
    }

    int Q;
//  cin>>Q;
    Q=read();

    while(Q--){
        int x1,y1,x2,y2;
//      cin>>x1>>y1>>x2>>y2;
        x1=read();
        y1=read();
        x2=read();
        y2=read();
        if(area(x1,y1,x2,y2)==(x2-x1+1)*(y2-y1+1)) puts("Yes");
        else puts("No");
    }

    return 0;
}

无人机航拍 题解

无人机航拍题解