专栏文章

题解：SP17123 IMBOX - Destroying the Weapon Warehouse

___CrossBow_EXE__
SP17123题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip7t4vq
此快照首次捕获于
2025/12/03 07:34
3 个月前
此快照最后确认于
2025/12/03 07:34
3 个月前
查看原文

前言

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

题意

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

题解

这道题目可以用扫描线轻松解决。
把问题简化，先看两个矩形的情况：
我们假想有一条扫描线，从下往上扫过整个图形。可以想象，当扫描线扫到每个矩形的上下两条边时，会是这样一个场景：
那么，我们就可以把原来的不规则图形给割成许多长方形，它的面积就是这些长方形的面积之和。我们只需要计算每个长方形的面积，最后加和即可。
接着，我们引入“入边”与“出边”的概念。对于每个矩形，扫描线一定会先扫到它的入边，再扫到它的出边。如果扫描线是从下往上扫，那么入边就是每个矩形的下底边，出边就是每个矩形的上底边。
不难看出，每个长方形的面积就是它的出入边长度乘上它的高度。高度很好求，重点就是出入边长度。具体地，我们要知道：在枚举时，应该有哪些出入边要乘上这个高。
说到这里，我们就可以把扫描线和线段树扯上关系了。我们把每个小长方形的横坐标先离散化一下，再放到一个数组 xx 中，如图：
我们可以用线段树来从 xx 数组上做手脚。我们在 xx 数组上建一棵线段树：
我们把每个出入边都增加一个权值的属性，入边为 11，出边为 −1-1。扫描线每次往上动，都把扫到的边所对应的区间给加上这条边的权值。
这样，每次扫到一个出入边，都把所在的长方形的高乘上线段树中值不为 00 的区间即可。
来看模拟的过程：
其中绿色代表已经算过的面积，线段树上的灰色代表值为 00，黄色代表区间修改。
扫描线的思想到这里就结束了。来看代码。

代码

我将会一点点解释每一部分的意义。
CPP
struct que{//边 
	int x1,x2,y,op;
	friend bool operator< (que a,que b){return a.y<b.y;} 
}q[N];
用来记录出入边的结构体，其中 x1x_1 和 x2x_2 表示这条线段的左右端点的横坐标，yy 代表这条边的高度，opop 代表权值。显然 op∈{1,−1}op \in \{1,-1\}。
CPP
struct node{
	int l,r,minn,sum,add;//minn为区间最小值，sum为最小值个数 
}tr[N<<2];
用来记录线段树上节点的结构体。注意数组开 44 倍。
CPP
vector<int> num;
int get(int x){//得到x离散化后的值 
	return lower_bound(num.begin(),num.end(),x)-num.begin();
}
用来离散化。其中 num 中存的是上面的 xx 数组。
CPP
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;
	}
}
向上传递最小值和最小值数量。它们的作用很巧妙：如果最小值是 00，那说明高不用乘这条边；如果最小值不是 00 那就得算。
CPP
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;
	}
}
因为是区间加所以需要下传懒标记。
CPP
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);
}
线段树的建树、区间加，不解释。
CPP
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_);
}
输入部分，并且把每条边的数据存到结构体中，再把横坐标存入 xx 数组。
CPP
sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());//离散化
对 xx 数组离散化，并去除多余元素。
CPP
build(1,0,num.size()-2);//建树
对 xx 数组建一棵线段树，注意左右端点。
CPP
sort(q+1,q+cnt+1);//对每一条边按y高度排序
把边按照 yy 坐标排序。
CPP
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;
关键部分！先算出整个图形的宽度，再枚举每个出入边，增加答案。
最后就是全部代码：
CPP
#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 大佬的图片和学习笔记！

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...