接下来利用一个例题来介绍扫描线。

P5490 【模板】扫描线

求 $n$ 个矩形的面积并。矩形以给定左下角坐标 $(x_1, y_1)$ ，右上角坐标 $(x_2, y_2)$ 的方式给出。

$1 \le n \le {10}^5$ ， $0 \le x_1 < x_2 \le {10}^9$ ， $0 \le y_1 < y_2 \le {10}^9$ 。

做法

可参考题解：【学习笔记】扫描线。此处不再赘述。

代码

毕竟自己的代码最符合自己的习惯的啦 $\sim$

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	#define ll long long
	const ll N=300005;//开大，一点要开大！ 
	ll n,cnt=0,seg=0,a[N*2],ans=0;
	struct Line{ll y,x1,x2,val;}l[N*2];//线段信息 
	struct SGT
	{
		#define lson (root*2)
		#define rson ((root*2)+1)
		#define mid ((l+r)/2)
		struct Node{ll data,cvr,l,r; Node(){data=cvr=l=r=0;}}t[N<<3];
		void pushup(ll root)
		{//核心操作。若被全覆盖，则长度为区间长度；否则，细分左右儿子查询。 
			if(t[root].data>=1)
				t[root].cvr=t[root].r-t[root].l;//在坐标轴中，线段并不包含右端点往后的一块。 
			else
				t[root].cvr=t[lson].cvr+t[rson].cvr;
		}
		void update(ll root,ll x,ll y,ll data)
		{
			//x，y 也是左闭右开的。 
			if(x<=t[root].l&&t[root].r<=y)//由于节点维护的是线段，所以这样处理。 
			{
				t[root].data+=data;//可行性：它的值加 1，必定有相应的抵消（-1）。 
				pushup(root);
				return;
			}//不用 mid 的原理同上两个注释。 
			if(x<t[lson].r) update(lson,x,y,data);//r 不能包括 x，不取等于。 
			if(y>t[rson].l) update(rson,x,y,data);//l 不能包括 y，不取等于。
			pushup(root);
		}
		void build(ll root,ll l,ll r)//给节点划定维护范围。 
		{
			//左闭右开的区间。
			//在坐标轴中，线段并不包含右端点往后的一块。所以如下处理可行。 
			t[root].l=a[l],t[root].r=a[r+1];//节点维护的是线段。 
			if(l==r) return;
			build(lson,l,mid);
			build(rson,mid+1,r);
		}
	}Tree;
	bool cmp(Line a,Line b){return a.y<b.y;}
	void yzmain()
	{
		ll x1,x2,y1,y2;
		scanf("%lld",&n);
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
			l[++cnt]=(Line){y1,x1,x2,1};
			l[++cnt]=(Line){y2,x1,x2,-1};
			a[++seg]=x1;a[++seg]=x2;
		}
		sort(l+1,l+cnt+1,cmp);
		sort(a+1,a+seg+1);//并用于去重。 
		seg=unique(a+1,a+seg+1)-(a+1)-1;//去重，得到不重元素个数。
		//iterator unique(iterator it_1,iterator it_2,[bool MyFunc]);
		//给有序列表去重，返回最后一个不重复元素的迭代器 +1。 
		//时间复杂度 O(n)。 
		Tree.build(1,1,seg);
		for(ll i=1;i<=cnt-1;i++)
		{
			Tree.update(1,l[i].x1,l[i].x2,l[i].val);
			ans+=(l[i+1].y-l[i].y)*Tree.t[1].cvr;
		}
		printf("%lld\n",ans);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

例题

P1856 [USACO5.5]矩形周长Picture

题意

所有矩形合并后的边长称为周长。求 $n$ 个矩形的周长。矩形以给定左下角坐标 $(x_1, y_1)$ ，右上角坐标 $(x_2, y_2)$ 的方式给出。

$1 \le n \le 5000$ ， $-10000 \le x_1 < x_2 \le 10000$ ， $-10000 \le y_1 < y_2 \le 10000$ 。

点击查看题解

题解

由于矩形有长和宽，所以建立两棵扫描线，向 $x$ 轴正方向扫一遍及向 $y$ 轴正方向扫一遍。

我们发现，当线段树中节点覆盖次数由 $0$ 变 $1$ 或由 $1$ 变 $0$ ，才会对周长产生贡献。因此，可以设定 $\Delta$ 为覆盖线段长度的变化量，累加到 $ans$ 即可。

代码中有注意事项，用注释 /**/ 括了起来。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	#define ll long long
	const ll N=10005,fix=15000;
	ll n,cnt=0,seg=0,a[N*2];
	ll x1[N],x2[N],y1[N],y2[N];
	struct Line{ll y,x1,x2,val;}l[N*2]; 
	struct SGT
	{
		#define lson (root*2)
		#define rson ((root*2)+1)
		#define mid ((l+r)/2)
		struct Node{ll data,cvr,l,r; Node(){data=cvr=l=r=0;}}t[N<<3];
		ll glen(ll l,ll r){return r-l;}
		void pushup(ll root)
		{
			if(t[root].data>=1)
				t[root].cvr=glen(t[root].l,t[root].r);
			else
				t[root].cvr=t[lson].cvr+t[rson].cvr;
		}
		void update(ll root,ll x,ll y,ll data)
		{
			if(x<=t[root].l&&t[root].r<=y)
			{
				t[root].data+=data;
				pushup(root);
				return;
			}
			if(x<t[lson].r) update(lson,x,y,data);
			if(y>t[rson].l) update(rson,x,y,data);
			pushup(root);
		}
		void build(ll root,ll l,ll r)
		{
			t[root].l=a[l],t[root].r=a[r+1];
			if(l==r) return;
			build(lson,l,mid);
			build(rson,mid+1,r);
		}
	}Tree1,Tree2;
	bool cmp(Line a,Line b)
	{
		/*让正边权先处理，应对正负边重合。 
		  使得这条边在线段树中一直被覆盖，防止重复统计。*/
		if(a.y==b.y) return a.val>b.val;
		return a.y<b.y;
	}
	ll solve1()
	{
		ll ans=0,dis=0;seg=0,cnt=0;
		for(int i=1;i<=n;i++)
		{
			l[++cnt]=(Line){y1[i],x1[i],x2[i],1};
			l[++cnt]=(Line){y2[i],x1[i],x2[i],-1};
			a[++seg]=x1[i];a[++seg]=x2[i];
		}
		sort(l+1,l+cnt+1,cmp);
		sort(a+1,a+seg+1);
		seg=unique(a+1,a+seg+1)-(a+1)-1;
		Tree1.build(1,1,seg);
		for(ll i=1;i<=cnt;i++)
		{
			dis=Tree1.t[1].cvr;
			Tree1.update(1,l[i].x1,l[i].x2,l[i].val);
			dis=abs(dis-Tree1.t[1].cvr);
			ans+=dis;
		}
		return ans;
	}
	ll solve2()
	{
		ll ans=0,dis=0;seg=0,cnt=0;
		for(int i=1;i<=n;i++)
		{
			l[++cnt]=(Line){x1[i],y1[i],y2[i],1};
			l[++cnt]=(Line){x2[i],y1[i],y2[i],-1};
			a[++seg]=y1[i];a[++seg]=y2[i];
		}
		sort(l+1,l+cnt+1,cmp);
		sort(a+1,a+seg+1);
		seg=unique(a+1,a+seg+1)-(a+1)-1;
		Tree2.build(1,1,seg);
		for(ll i=1;i<=cnt;i++)
		{
			dis=Tree2.t[1].cvr;
			Tree2.update(1,l[i].x1,l[i].x2,l[i].val);
			dis=abs(dis-Tree2.t[1].cvr);
			ans+=dis;
		}
		return ans;
	}
	void yzmain()
	{
		scanf("%lld",&n);
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld%lld%lld%lld",&x1[i],&y1[i],&x2[i],&y2[i]);
			x1[i]+=fix;x2[i]+=fix;y1[i]+=fix;y2[i]+=fix;
		}
		printf("%lld\n",solve1()+solve2());
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/fb2984b64d7e/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 树线段树扫描线

最后更新：2023-08-21, 23:18:21

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158