题解：SP17123 IMBOX - Destroying the Weapon Warehouse

· · 题解

前言

扫描线板子题。与 P5490 完全一样，可以当双倍经验。

题意

给你 n 个矩形的四个角的坐标，把所有矩形拼成一个大的不规则图形，求这个不规则图形的面积。

题解

这道题目可以用扫描线轻松解决。

把问题简化，先看两个矩形的情况：

我们假想有一条扫描线，从下往上扫过整个图形。可以想象，当扫描线扫到每个矩形的上下两条边时，会是这样一个场景：

那么，我们就可以把原来的不规则图形给割成许多长方形，它的面积就是这些长方形的面积之和。我们只需要计算每个长方形的面积，最后加和即可。

接着，我们引入“入边”与“出边”的概念。对于每个矩形，扫描线一定会先扫到它的入边，再扫到它的出边。如果扫描线是从下往上扫，那么入边就是每个矩形的下底边，出边就是每个矩形的上底边。

不难看出，每个长方形的面积就是它的出入边长度乘上它的高度。高度很好求，重点就是出入边长度。具体地，我们要知道：在枚举时，应该有哪些出入边要乘上这个高。

说到这里，我们就可以把扫描线和线段树扯上关系了。我们把每个小长方形的横坐标先离散化一下，再放到一个数组 x 中，如图：

我们可以用线段树来从 x 数组上做手脚。我们在 x 数组上建一棵线段树：

我们把每个出入边都增加一个权值的属性，入边为 1，出边为 -1。扫描线每次往上动，都把扫到的边所对应的区间给加上这条边的权值。

这样，每次扫到一个出入边，都把所在的长方形的高乘上线段树中值不为 0 的区间即可。

来看模拟的过程：

其中绿色代表已经算过的面积，线段树上的灰色代表值为 0，黄色代表区间修改。

扫描线的思想到这里就结束了。来看代码。

代码

我将会一点点解释每一部分的意义。

struct que{//边 
    int x1,x2,y,op;
    friend bool operator< (que a,que b){return a.y<b.y;} 
}q[N];

用来记录出入边的结构体，其中 x_1 和 x_2 表示这条线段的左右端点的横坐标，y 代表这条边的高度，op 代表权值。显然 op \in \{1,-1\}。

struct node{
    int l,r,minn,sum,add;//minn为区间最小值，sum为最小值个数 
}tr[N<<2];

用来记录线段树上节点的结构体。注意数组开 4 倍。

vector<int> num;
int get(int x){//得到x离散化后的值 
    return lower_bound(num.begin(),num.end(),x)-num.begin();
}

用来离散化。其中 num 中存的是上面的 x 数组。

void pushup(int u){
    if(tr[ls].minn==tr[rs].minn){//最小值一样 
        tr[u].minn=tr[ls].minn;//最小值传递 
        tr[u].sum=tr[ls].sum+tr[rs].sum;//数量相加 
    }else if(tr[ls].minn<tr[rs].minn){
        tr[u].minn=tr[ls].minn;
        tr[u].sum=tr[ls].sum;
    }else{
        tr[u].minn=tr[rs].minn;
        tr[u].sum=tr[rs].sum;
    }
}

向上传递最小值和最小值数量。它们的作用很巧妙：如果最小值是 0，那说明高不用乘这条边；如果最小值不是 0 那就得算。

void pushdown(int u){//下传懒标记 
    if(tr[u].add!=0){
        tr[ls].minn+=tr[u].add;
        tr[rs].minn+=tr[u].add;
        tr[ls].add+=tr[u].add;
        tr[rs].add+=tr[u].add;
        tr[u].add=0;
    }
}

因为是区间加所以需要下传懒标记。

void build(int u,int l,int r){
    tr[u].l=l;tr[u].r=r;
    if(l==r){
        tr[u].minn=0;//开始没有出入边 
        tr[u].sum=num[l+1]-num[l];//相邻两个竖着的边的距离 
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(u);
}
void modify(int u,int l,int r,int x){//区间加 
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].minn+=x;
        tr[u].add+=x;
        return;
    }
    pushdown(u);
    int mid=(tr[u].l+tr[u].r)>>1;
    if(mid>=l) modify(ls,l,r,x);
    if(mid<r) modify(rs,l,r,x);
    pushup(u);
}

线段树的建树、区间加，不解释。

cin>>n;
for(int i=1,x,y,x_,y_;i<=n;i++){
    cin>>x>>y>>x_>>y_;
    q[++cnt]={x,x_,y,1};//入边为1 
    q[++cnt]={x,x_,y_,-1};//出边为-1 
    num.push_back(x);//放进用于离散化的vector 
    num.push_back(x_);
}

输入部分，并且把每条边的数据存到结构体中，再把横坐标存入 x 数组。

sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());//离散化

对 x 数组离散化，并去除多余元素。

build(1,0,num.size()-2);//建树

对 x 数组建一棵线段树，注意左右端点。

sort(q+1,q+cnt+1);//对每一条边按y高度排序

把边按照 y 坐标排序。

int tot=num.back()-num.front();//整个图形的宽度 
for(int i=1;i<cnt;i++){//不看最后一个 
    modify(1,get(q[i].x1),get(q[i].x2)-1,q[i].op);//入边则区间+1，出边则区间-1 
    if(tr[1].minn==0) ans+=(tot-tr[1].sum)*(q[i+1].y-q[i].y);//不被所有矩形包含，不在矩形内，答案加上非0的个数乘纵坐标之差 
    else ans+=tot*(q[i+1].y-q[i].y);//在矩形内，直接长乘高算面积 
}
cout<<ans<<endl;

关键部分！先算出整个图形的宽度，再枚举每个出入边，增加答案。

最后就是全部代码：

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define ls (u<<1)
#define rs (u<<1|1)
#define int long long
using namespace std;
const int N=200005;
int n,cnt=0,ans=0;
struct que{//边 
    int x1,x2,y,op;
    friend bool operator< (que a,que b){return a.y<b.y;} 
}q[N];
struct node{
    int l,r,minn,sum,add;//minn为区间最小值，sum为最小值个数 
}tr[N<<2];
vector<int> num;
int get(int x){//得到x离散化后的值 
    return lower_bound(num.begin(),num.end(),x)-num.begin();
}
void pushup(int u){
    if(tr[ls].minn==tr[rs].minn){//最小值一样 
        tr[u].minn=tr[ls].minn;//最小值传递 
        tr[u].sum=tr[ls].sum+tr[rs].sum;//数量相加 
    }else if(tr[ls].minn<tr[rs].minn){
        tr[u].minn=tr[ls].minn;
        tr[u].sum=tr[ls].sum;
    }else{
        tr[u].minn=tr[rs].minn;
        tr[u].sum=tr[rs].sum;
    }
}
void pushdown(int u){//下传懒标记 
    if(tr[u].add!=0){
        tr[ls].minn+=tr[u].add;
        tr[rs].minn+=tr[u].add;
        tr[ls].add+=tr[u].add;
        tr[rs].add+=tr[u].add;
        tr[u].add=0;
    }
}
void build(int u,int l,int r){
    tr[u].l=l;tr[u].r=r;
    if(l==r){
        tr[u].minn=0;//开始没有出入边 
        tr[u].sum=num[l+1]-num[l];//相邻两个竖着的边的距离 
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(u);
}
void modify(int u,int l,int r,int x){//区间加 
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].minn+=x;
        tr[u].add+=x;
        return;
    }
    pushdown(u);
    int mid=(tr[u].l+tr[u].r)>>1;
    if(mid>=l) modify(ls,l,r,x);
    if(mid<r) modify(rs,l,r,x);
    pushup(u);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    cin>>n;
    for(int i=1,x,y,x_,y_;i<=n;i++){
        cin>>x>>y>>x_>>y_;
        q[++cnt]={x,x_,y,1};//入边为1 
        q[++cnt]={x,x_,y_,-1};//出边为-1 
        num.push_back(x);//放进用于离散化的vector 
        num.push_back(x_);
    }
    sort(num.begin(),num.end());
    num.erase(unique(num.begin(),num.end()),num.end());//离散化 
    build(1,0,num.size()-2);//建树 
    sort(q+1,q+cnt+1);//对每一条边按y高度排序 
    int tot=num.back()-num.front();//整个图形的宽度 
    for(int i=1;i<cnt;i++){//不看最后一个
        modify(1,get(q[i].x1),get(q[i].x2)-1,q[i].op);//入边则区间+1，出边则区间-1 
        if(tr[1].minn==0) ans+=(tot-tr[1].sum)*(q[i+1].y-q[i].y);//不被所有矩形包含，不在矩形内，答案加上非0的个数乘纵坐标之差 
        else ans+=tot*(q[i+1].y-q[i].y);//在矩形内，直接长乘高算面积 
    }
    cout<<ans<<endl;
    return 0;
}

致谢

感谢 @NCC79601 大佬的图片和学习笔记！