POJ1177-线段树(扫描线求周长)

题目链接

Poj1177

思路

裸的线段树扫描线题目了。
首先考虑把单独的一条边独立出来，然后思考周长怎么求?
很显然，在加入一条横边时，我们考虑它的贡献，也就是之前的横轴上没有覆盖的区域。
考虑竖边，竖边一定由相邻两条横着的边构成，我们取上一条加入的横边与当前考虑加入的横边。
他们各自的高也就是一段竖边的高，但是有多少段呢？画一下可以发现，有多少段取决于全部区域内有多少块不连接的区域，例如[2,3],[5,6]，则一共有4条，因为每块区域提供两条，而[1,2][2,4]的话只有两条，因为只有1块区域。
注意：这里讨论的竖边并不是长方形的完全竖边，而是我们把它分段了，一段一段的加上去。
经过上面分析，我们线段树上需要维护的有
1.当前覆盖的区域的长度和val
2.区域的块数，也就是不相连接的部分的数量num
3.当前区域被覆盖的次数s,如果s为0，则这个点对应的区间已经扫描过了，答案已经加上了。s不可能小于0.

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include<algorithm>
#include <cmath>
using namespace std;
#define ll long long 
const int N = 5e3+10;
const int inf = 0x3f3f;
struct line
{
	int l,r;
	int in;
	int h;
	bool operator < (const line a)const
	{
	return h<a.h;
	}
}edge[N*10];
struct node
{
	int l,r;
	int s;
	bool lc,rc;
	int val;
	int num;
	int len()
	{
		return r-l+1;
	}
}tree[N*40];
void PushUp(int rt)
{
	if(tree[rt].s)//该区间完全被覆盖 
	{
		tree[rt]. val=tree[rt].len();
		tree[rt].lc=tree[rt].rc=1;
		tree[rt].num = 1;
	}
	else if(tree[rt].l==tree[rt].r)
	{
		tree[rt].val = 0;
		tree[rt].lc=tree[rt].rc=0;
		tree[rt].num=0;
	}
	else
	{
		tree[rt].val=tree[rt<<1].val+tree[rt<<1|1].val;
		tree[rt].lc=tree[rt<<1].lc;
		tree[rt].rc=tree[rt<<1|1].rc;
		tree[rt].num=tree[rt<<1].num+tree[rt<<1|1].num-(tree[rt<<1].rc&tree[rt<<1|1].lc);
	}
}
void build(int rt,int l,int r)
{
	tree[rt].l=l;
	tree[rt].r=r;
	tree[rt].s=tree[rt].val=0;
	tree[rt].lc=tree[rt].rc=tree[rt].num=0;
	if(l==r)return ;
	int mid = (l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r); 
}
void update(int rt,int l,int r,int c)
{   if(tree[rt].l>r||tree[rt].r<l)return ;
	if(tree[rt].l>=l&&tree[rt].r<=r)
	{
		tree[rt].s+=c;
		PushUp(rt);
		return ;
	}
	update(rt<<1,l,r,c);
	update(rt<<1|1,l,r,c);
	PushUp(rt);
}
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		int x1,x2,y1,y2;
		int mx = -inf;
		int mi = inf;
		int tot = 0;
		for(int i=0;i<n;i++)
		{
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			mx=max(mx,max(x1,x2));
			mi=min(mi,min(x1,x2));
			edge[tot].l=edge[tot+1].l=x1;
			edge[tot].r=edge[tot+1].r=x2;
			edge[tot].in=1;
			edge[tot+1].in=-1;
			edge[tot].h=y1;
			edge[tot+1].h=y2;
			tot+=2;
		}
		sort(edge,edge+tot);
		int ans = 0;
		int last = 0;
		build(1,mi,mx);
		for(int i=0;i<tot;i++)
		{
			update(1,edge[i].l,edge[i].r-1,edge[i].in);
			ans+=abs(tree[1].val-last);
			ans+=(edge[i+1].h-edge[i].h)*2*tree[1].num;
			last = tree[1].val;
		}
		printf("%d\n",ans);
	}
}