【学习笔记】扫描线

备战 NOIP 2022 填坑ing...

扫描线

思想就是把横边从小到大sort，拿条线从下往上扫，扫到横边算一下长度，再乘上两条横边的高度差，因为要求 \(O(nlogn)\) 的时间复杂度所以用线段树实现（还要对横坐标进行离散化）

还有就是空间要开大一点，最好开8倍（板子题我开了16倍）

先贴个板子，这篇博客主要记录有关的题

void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	if(l==r) return ;
	int mid=(t[p].l+t[p].r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}

void push_up(int p)
{
	if(t[p].cnt) t[p].len=(x[t[p].r+1]-x[t[p].l]);
	else t[p].len=t[p*2].len+t[p*2+1].len;
}

void update(int p,int l,int r,int val)
{
	if(x[t[p].r+1]<=l || x[t[p].l]>=r) return ;
	if(l<=x[t[p].l] && x[t[p].r+1]<=r)
	{
		t[p].cnt+=val;
		push_up(p);
		return ;
	}
	update(p*2,l,r,val);
	update(p*2+1,l,r,val);
	push_up(p);
}

void work()
{
	for(int i=1;i<=n;i++)
	{
		int x1,y1,x2,y2;
		x1=read(),y1=read();
		x2=read(),y2=read();
		if(y1>y2) swap(y1,y2);
		x[i*2-1]=x1,x[i*2]=x2;
		line[i*2-1]={x1,x2,y1,1};
		line[i*2]={x1,x2,y2,-1};
	}
	
	n<<=1;sort(x+1,x+n+1);
	sort(line+1,line+n+1,cmp);
	int num=unique(x+1,x+n+1)-x-1;
	
	build(1,1,num-1);int ans=0;

	for(int i=1;i<n;i++)
	{
		update(1,line[i].l,line[i].r,line[i].val);
		ans+=t[1].len*(line[i+1].h-line[i].h);
	}
	
	printf("%lld",ans);
}

[IOI 1998] Picture

求周长并板子题