poj3277_code.txt

问题：求平面上多个矩形的总面积。 算法：线段树（经典的线段树题目）

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 500020
int b[maxn],e[maxn],lson[maxn],rson[maxn],cnt[maxn],m[maxn],lbd[maxn],rbd[maxn],line[maxn];
int root,n,nn;
struct node
{
	int x,y1,y2,index;
	int left;
};
node seg[maxn];
int ymap[maxn],used[maxn];
void build(int l,int r)
{
	n++;
	int v=n;
	b[v]=l;e[v]=r;
	if(r-l>1)
	{
		lson[v]=n+1;
		build(l,(l+r)/2);
		rson[v]=n+1;
		build((l+r)/2,r);
	}
	return ;
}
void updatem(int v)
{
	if(cnt[v]>0)m[v]=ymap[e[v]]-ymap[b[v]];
	else
	{
		if(e[v]-b[v]==1)m[v]=0;
		else m[v]=m[lson[v]]+m[rson[v]];
	}
//	printf("%d %d %d\n",v,cnt[v],m[v]);
	return ;
}
void updateline(int v)
{
	if(cnt[v]>0)lbd[v]=rbd[v]=line[v]=1;
	else 
	{
		if(e[v]-b[v]==1)lbd[v]=rbd[v]=line[v]=0;
		else
		{
			lbd[v]=lbd[lson[v]];
			rbd[v]=rbd[rson[v]];
			line[v]=line[lson[v]]+line[rson[v]]-rbd[lson[v]]*lbd[rson[v]];
		}
	}
//	printf("%d %d %d %d lbd\n",v,lbd[v],rbd[v],line[v]);
	return ;
}
void insert(int l,int r,int v)
{
	if(!v)return ;
	if(l<=ymap[b[v]]&&ymap[e[v]]<=r)
	{
		cnt[v]++;
		lbd[v]=rbd[v]=1;
	}
	else if(e[v]-b[v]>1)
	{
		if(l<ymap[(b[v]+e[v])/2])insert(l,r,lson[v]);
		if(r>ymap[(b[v]+e[v])/2])insert(l,r,rson[v]);
	}
	updatem(v);
	updateline(v);
	return ;
}
void del(int l,int r,int v)
{
	if(!v)return ;
	if(l<=ymap[b[v]]&&ymap[e[v]]<=r)
	{
		cnt[v]--;
		if(l==ymap[b[v]])lbd[v]=0;
		if(r==ymap[e[v]])rbd[v]=0;
	}
	else if(e[v]-b[v]>1)
	{
		if(l<ymap[(b[v]+e[v])/2])del(l,r,lson[v]);
		if(r>ymap[(b[v]+e[v])/2])del(l,r,rson[v]);
	}
	updatem(v);
	updateline(v);
	return ;
}
bool cmp(node a,node b)
{
	return (a.x<b.x)||(a.x==b.x&&a.y1<b.y1);
}
void solve()
{
	root=1;n=0;
	memset(lson,0,sizeof(lson));memset(rson,0,sizeof(rson));
	memset(cnt,0,sizeof(cnt));memset(m,0,sizeof(m));
	memset(line,0,sizeof(line));
	memset(lbd,0,sizeof(lbd));memset(rbd,0,sizeof(rbd));
	memset(used,0,sizeof(used));
	sort(ymap,ymap+nn*2);
	int tn=std::unique(ymap,ymap+nn*2)-ymap;
	build(0,tn-1);
	sort(seg,seg+nn*2,cmp);
	int prem,prel,i;
	__int64 ans=0;
//	for(i=0;i<=n;i++)printf("%d %d %d %d\n",i,b[i],e[i],cnt[i]);
	insert(seg[0].y1,seg[0].y2,1);
	prem=m[1];prel=line[1];
//	used[seg[0].index]=1;
//	ans+=prem;
//	printf("%d %d |",nn,ans);
//	printf("%d ans %d %d   line:::%d \n",ans,seg[0].y1,seg[0].y2,line[1]);
	for(i=1;i<nn*2;i++)
	{
		if(seg[i].left)
		{
			insert(seg[i].y1,seg[i].y2,1);
		}
		else
		{
//			printf("delete  ");
			del(seg[i].y1,seg[i].y2,1);
		}
		ans+=(__int64)prem*(seg[i].x-seg[i-1].x);
	//	ans+=prel*(seg[i].x-seg[i-1].x)*2;
//		printf("%d %d %d %d %d %d\n",i,seg[i].x,seg[i-1].x,ans,m[1],prem);
		prem=m[1];prel=line[1];	 
	}
	printf("%I64d\n",ans);
	return ;
}
int main()
{
//	freopen("in.txt","r",stdin);
	
	int i,x1,x2,y1,y2;
	int a,b,c;
	scanf("%d",&nn);
	for(i=0;i<2*nn;i+=2)
	{
		scanf("%d%d%d",&a,&b,&c);
		x1=a;x2=b;y1=0;y2=c;
		ymap[i]=y1;ymap[i+1]=y2;
		seg[i].index=i;
		seg[i].x=x1;seg[i].y1=y1;seg[i].y2=y2;
		seg[i].left=1;
		seg[i+1].index=i;
		seg[i+1].x=x2;seg[i+1].y1=y1;seg[i+1].y2=y2;
		seg[i+1].left=0;
	}
	if(nn==0)
	{
		printf("0\n");return 0;
	}
	solve();
	return 0;
}