线段树样例.cpp

线段树的样例程序

//*线段树样例*//
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MAX 10010
struct SEG
{
	int B,E;
	int count;
	int leftchild,rightchild;
	int leftcover,rightcover;
	int segment;
	int len;
}seg[2*MAX];

struct RECT
{
	int top,end;
	int x;
	bool tag;
}rect[MAX];

int index[MAX];
int temp[MAX];
int t;
int counter;
int N;


int comprect(const void* e1,const void* e2)
{
	RECT* p1=(RECT*)e1;
	RECT* p2=(RECT*)e2;
	return p1->x - p2->x;
}

int compy(const void* e1,const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}

void Build(int from,int to)
{
	int v;
	t++;
	v= t;
	seg[v].B=from;
	seg[v].E=to;
	seg[v].count=seg[v].len=0;
	seg[v].leftcover=seg[v].rightcover=0;
	if(to - from>1)
	{
		seg[v].leftchild = t+1;
		Build(from,(from+to)/2);
		seg[v].rightchild = t+1;
		Build((from+to)/2,to);
	}
}

int getindex(int key)
{
	int *p;
	p = (int *) bsearch(&key,index,counter,sizeof(int),compy);
	if(p == NULL)
		return 0;
	else
		return (p - index + 1);
}

void Updata(int v,int from,int to)
{
	if(seg[v].count>0)
	{
		seg[v].len = index[seg[v].E-1] - index[seg[v].B-1];
		seg[v].leftcover = seg[v].rightcover = 1;
		seg[v].segment = 1;
	}
	else if(to - from > 1 )
	{
		seg[v].len = seg[seg[v].leftchild].len + seg[seg[v].rightchild].len;
		seg[v].leftcover = seg[seg[v].leftchild].leftcover;
		seg[v].rightcover = seg[seg[v].rightchild].rightcover;
		seg[v].segment = seg[seg[v].leftchild].segment + seg[seg[v].rightchild].segment
			- seg[seg[v].rightchild].leftcover * seg[seg[v].leftchild].rightcover;
	}
	else
	{
		seg[v].len=0;
		seg[v].leftcover = seg[v].rightcover=0;
		seg[v].segment=0;
	}
}

void Insert(int v,int from,int to)
{
	if(from <= seg[v].B && seg[v].E <=to)
	{
		seg[v].count++;
	}
	else
	{
		if(from < (seg[v].B + seg[v].E)/2)
			Insert(seg[v].leftchild,from,to);
		if(to > (seg[v].B + seg[v].E)/2)
			Insert(seg[v].rightchild,from,to);
	}
	Updata(v,seg[v].B,seg[v].E);
}

void Del(int v,int from,int to)
{
	if(from <= seg[v].B && seg[v].E <=to)
	{
		seg[v].count--;
	}
	else
	{
		if(from < ((seg[v].B + seg[v].E)/2))
			Del(seg[v].leftchild,from,to);
		if(to > ((seg[v].B + seg[v].E)/2))
			Del(seg[v].rightchild,from,to);
	}
	Updata(v,seg[v].B,seg[v].E);
}

int main()
{
	//freopen("1.txt","r",stdin);
	int i;
	int x1,y1,x2,y2;
	int C,pre;
	int left,right;

	scanf("%d",&N);
	for(i=0 ; i<N;i++)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		rect[2*i].top=y1;
		rect[2*i].end=y2;
		rect[2*i].tag=true;
		rect[2*i].x=x1;

		rect[2*i+1].top=y1;
		rect[2*i+1].end=y2;
		rect[2*i+1].tag=false;
		rect[2*i+1].x=x2;

		temp[2*i]=y1;
		temp[2*i+1]=y2;
	}
	qsort(rect,2*N,sizeof(RECT),comprect);
	qsort(temp,2*N,sizeof(int),compy);
	counter=0;
	index[counter++]=temp[0];
	for(i=1;i<2*N;i++)
	{
		if(temp[i] != index[counter-1])
		{
			index[counter++]=temp[i];
		}
	}

	t=0;
	Build(1,counter);
	C= pre=0;
	for(i=0;i<2*N-1;i++)
	{
		left = getindex(rect[i].top);
		right = getindex(rect[i].end);
		if(rect[i].tag)
		{
			Insert(1,left,right);
		}
		else
		{
			Del(1,left,right);
		}
		C += 2*(rect[i+1].x - rect[i].x)* seg[1].segment;
		if(seg[1].len >= pre)
		{
			C += (seg[1].len - pre);
		}
		else
		{
			C -= (seg[1].len - pre);
		}
		pre = seg[1].len;
	}
	left = getindex(rect[i].top);
	right = getindex(rect[i].end);
	Del(1,left,right);
	if(seg[1].len >= pre)
	{
		C += (seg[1].len - pre);
	}
	else
	{
		C -= (seg[1].len - pre);
	}
	printf("%d\n",C);
	return 0;
}