扫描线学习笔记

前言

扫描线思想可以在 \(O(n^2)\) 的时间复杂度内进行二维平面的计算，运用线段树优化可以在 \(O(n \log n)\) 的时间复杂度内解决。

简介

P5490 【模板】扫描线

以此题为例，介绍扫描线。

最直接的想法是将每个正方形的面积先加起来，最后再减去重叠部分，但是代码难度较大，不易于实现。

用扫描线的思想，将二维转换为两个一维。对于 y 轴的一维，从下往上进行扫描，每一条扫描线就是矩形的长，用结构体记录起始终止的 x 值，以及 y 值，还有标记是矩形的上面长还是下面的长。

对于从左到右的另一维 x，用线段树维护每一个中间的区间，遇到扫描线时进行统计计算即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e6+20;
ll n,x_,x__,y_,y__,X[maxn],ans;
struct smx{
	ll l,r,h,flag;
	inline bool operator < (const smx &T) const{
		return h<T.h;
	}
}line[maxn];
struct segment{
	ll l,r,sum,cnt;
}tree[maxn<<3];
inline ll ls(ll p){
	return p<<1;
}
inline ll rs(ll p){
	return p<<1|1;
}
void build(ll p,ll l,ll r){
	tree[p].l=l,tree[p].r=r,tree[p].sum=tree[p].cnt=0;
	if(l==r) return;
	ll mid=l+r>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
} 
inline void push_up(ll p){
	if(tree[p].cnt){
		tree[p].sum=X[tree[p].r+1]-X[tree[p].l];
	}
	else tree[p].sum=tree[ls(p)].sum+tree[rs(p)].sum; 
}
void update(ll p,ll l,ll r,ll x,ll y,ll k){
	if(X[r+1]<=x||X[l]>=y) return;
	if(X[l]>=x&&X[r+1]<=y){
		tree[p].cnt+=k;
		push_up(p);//一定要写这行！！！ 
		return;
	}
	ll mid=l+r>>1;
	update(ls(p),l,mid,x,y,k);
	update(rs(p),mid+1,r,x,y,k);
	push_up(p);
}
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld%lld",&x_,&y_,&x__,&y__);
		X[i*2-1]=x_,X[i*2]=x__;
		line[i*2-1]=(smx){x_,x__,y_,1},line[i*2]=(smx){x_,x__,y__,-1};
	}
	n<<=1;
	sort(line+1,line+n+1);
	sort(X+1,X+n+1);
	ll tot=unique(X+1,X+n+1)-X-1;
	build(1,1,tot-1);
	for(int i=1;i<n;i++){
		update(1,1,tot-1,line[i].l,line[i].r,line[i].flag);
		ans+=(line[i+1].h-line[i].h)*tree[1].sum;
	}
	printf("%lld\n",ans);
	return 0;
} 

总结

可见扫描线可以处理二维的问题，所以遇到一些平面内的二维数点计算问题时，可以尝试用扫描线求解。