题解：P9284 [AGM 2023 资格赛] 海盗

· · 题解

扫描线加线段树好题。

题意

给 B 次矩形覆盖，求 S 条线段的覆盖情况。

思路

看到矩形覆盖容易想到扫描线。将 S 条线段分类讨论，分为横向和纵向的线段。

以考虑横向线段为例，我们维护一棵线段树，遍历衡坐标，则每个矩形的上边界可以视为一段区间加一。同理，下边界是区间减一操作。区间操作完进行查询即可。

问题在于如何通过区间查询快速获取线段覆盖情况。如果一段线段被部分覆盖或没有覆盖，则区间最小值为零。而如果线段部分覆盖或全部覆盖，区间最大值不为零。因此，我们只需维护区间最值即可。

时间复杂度 O((B+S)\log N)。

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define sc scanf
#define pr printf
#define v1 first
#define v2 second
#define f(nm1,nm2,nm3) for(int nm1=nm2; nm1<= nm3; nm1++)
#define lowbit(x) (x&(-x))
#define lson k*2,l,mid
#define rson k*2+1,mid+1,r
#define mid ((l+r)>>1)
int n,m;
struct bin{//线段树封装
    int maxn[400005],minn[400005],lazy[400005];
    void build(int k,int l,int r){//建树
        lazy[k]=0;
        if(l==r){
            maxn[k]=0;
            minn[k]=0;
            return;
        }
        maxn[k]=max(maxn[k*2],maxn[k*2+1]);
        minn[k]=min(minn[k*2],minn[k*2+1]);
    }
    void push_down(int k,int l,int r){//下传懒标记
        if(!lazy[k])
            return;
        maxn[k*2]+=lazy[k];
        minn[k*2]+=lazy[k];
        maxn[k*2+1]+=lazy[k];
        minn[k*2+1]+=lazy[k];
        lazy[k*2]+=lazy[k];
        lazy[k*2+1]+=lazy[k];
        lazy[k]=0;
    }
    void modify(int k,int l,int r,int lbor,int rbor,int val){//区间加法
        if(lbor<=l&&r<=rbor){
            maxn[k]+=val;
            minn[k]+=val;
            lazy[k]+=val;
            return;
        }
        push_down(k,l,r);
        if(mid>=lbor){
            modify(lson,lbor,rbor,val);
        }
        if(mid<rbor){
            modify(rson,lbor,rbor,val);
        }
        maxn[k]=max(maxn[k*2],maxn[k*2+1]);
        minn[k]=min(minn[k*2],minn[k*2+1]);
    }
    pair<int,int> query(int k,int l,int r,int lbor,int rbor){//查询区间最值
        if(lbor<=l&&r<=rbor)
            return {maxn[k],minn[k]};
        push_down(k,l,r);
        pair<int,int> ans={0,INF};
        if(lbor<=mid){
            auto res=query(lson,lbor,rbor);
            ans.v1=max(ans.v1,res.v1);
            ans.v2=min(ans.v2,res.v2);
        }
        if(rbor>mid){
            auto res=query(rson,lbor,rbor);
            ans.v1=max(ans.v1,res.v1);
            ans.v2=min(ans.v2,res.v2);
        }
        return ans;
    }
}b1,b2;
int b;
vector<pair<pair<int,int>,int>> vv1[100005],vv2[100005],q1[100005],q2[100005];
int ans[200005];
#undef x1
#undef y1
int main()
{
    sc("%d%d",&n,&m);
    sc("%d",&b);
    for(int i=1,x1,y1,x2,y2; i <= b; i++){
        sc("%d%d%d%d",&x1,&y1,&x2,&y2);
        vv1[x1].push_back({{y1,y2},1});//x1的位置区间加1
        vv1[x2+1].push_back({{y1,y2},-1});//x2+1的位置区间减1
        vv2[y1].push_back({{x1,x2},1});//同理
        vv2[y2+1].push_back({{x1,x2},-1});
    }
    int s;
    sc("%d",&s);
    for(int i=1,op,x,y,z; i <= s; i++){
        sc("%d%d%d%d",&op,&x,&y,&z);
        if(op==1)
            q1[x].push_back({{y,z},i});//查询操作
        else
            q2[x].push_back({{y,z},i});
    }
    b1.build(1,1,m);
    for(int i=1; i <= n; i++){//维护衡坐标
        for(auto y:vv1[i])
            b1.modify(1,1,m,y.v1.v1,y.v1.v2,y.v2);//区间修改
        for(auto y:q1[i]){
            auto res=b1.query(1,1,m,y.v1.v1,y.v1.v2);//区间查询
            if(res.v1==0){
                ans[y.v2]=0;//没有被覆盖
            }
            else if(res.v2==0){
                ans[y.v2]=1;//部分覆盖
            }
            else{
                ans[y.v2]=2;//完全覆盖
            }
        }
    }
    b2.build(1,1,n);
    for(int i=1; i <= m; i++){
        for(auto y:vv2[i])
            b2.modify(1,1,n,y.v1.v1,y.v1.v2,y.v2);
        for(auto y:q2[i]){
            auto res=b2.query(1,1,n,y.v1.v1,y.v1.v2);
            if(res.v1==0){
                ans[y.v2]=0;
            }
            else if(res.v2==0){
                ans[y.v2]=1;
            }
            else{
                ans[y.v2]=2;
            }
        }
    }
    for(int i=1; i <= s; i++){//输出
        if(ans[i]==0){
            pr("MISS\n");
        }
        else if(ans[i]==1){
            pr("HIT\n");
        }
        else{
            pr("SUNK\n");
        }
    }
    return 0;
}