pic-线段树.txt

总共80多道题的POJ详细解题报告

#include <iostream.h>
#include <stdlib.h>
int  t,b[20002],e[20002],count[20002],len[20002],leftchild[20002],rightchild[20002];
int segment[20002],leftcover[20002],rightcover[20002];
//author:Chen Kun [e-mail]
//注意：使用线段树要注意上界范围，比如1-N，可能占的空间
//为N(1+1/2+1/4+...)=N*2
int num,pre,peri,left,right,top;
int x1,y1,x2,y2;

struct rect
{
	int start,end,pos;bool tag;
}/*horizon[10002],*/vertical[10002];
int index[10002],temp[10002];
int cmp(const void*p1,const void*p2)
{
	rect i=*(rect*)p1;
	rect j=*(rect*)p2;
	return (i.pos-j.pos);
}
int cmpint(const void* p1,const void* p2)
{
	return (*(int*)p1-*(int*)p2);
}
int lookup(int key) 
{ 
   int *itemptr; 

   /* The cast of (int(*)(const void *,const void*)) 
      is needed to avoid a type mismatch error at 
      compile time */ 
   itemptr = (int *)bsearch (&key, index, top, sizeof(int),cmpint); 
   if(itemptr==NULL)
	   return 0;
   return (itemptr-index+1); 
} 
//build the segment-tree
void build(int x,int y)
{
	int v;
    t++;v=t;
    b[v]=x;e[v]=y;
    count[v]=0;len[v]=0;
	leftcover[v]=rightcover[v]=0;
    if(y-x>1)
	{
		leftchild[v]=t+1;build(x,(x+y)/2);
		rightchild[v]=t+1;build((x+y)/2,y);
	}
}
//updata the count and segment
void updata(int v,int x,int y)
{
	if (count[v]>0) 
	{
		len[v]=index[e[v]-1]-index[b[v]-1];
		leftcover[v]=rightcover[v]=1;
		segment[v]=1;
	}
	else if (y-x>1) 
	{
		len[v]=len[leftchild[v]]+len[rightchild[v]];
		leftcover[v]=leftcover[leftchild[v]];
		rightcover[v]=rightcover[rightchild[v]];
		segment[v]=segment[leftchild[v]]+segment[rightchild[v]]
			-leftcover[rightchild[v]]*rightcover[leftchild[v]];
	}
	else
	{
		len[v]=0;
		leftcover[v]=rightcover[v]=0;
		segment[v]=0;
	}
	
}
//insert interval [x,y] to node v
void insert(int v,int x,int y)
{
    if (x<=b[v]&&e[v]<=y)  count[v]++;
    else 
	{
		if (x<(b[v]+e[v])/2)  insert(leftchild[v],x,y);
		if (y>(b[v]+e[v])/2)  insert(rightchild[v],x,y);
    }
    updata(v,b[v],e[v]);
}
//delete interval [x,y] from node v
void del(int v,int x,int y)
{
    if (x<=b[v]&&e[v]<=y) count[v]--;
    else 
	{
		if (x<(b[v]+e[v])/2) del(leftchild[v],x,y);
		if (y>(b[v]+e[v])/2) del(rightchild[v],x,y);
    }
    updata(v,b[v],e[v]);
}


/*test for segment tree
int main()
{
	int i;
	t=0;
	build(1,10);
	
	insert(1,2,7);
	for(i=1;i<=t;i++)
		cout<<b[i]<<' '<<e[i]<<' '<<count[i]<<' '<<len[i]<<' '<<leftcover[i]<<' '<<rightcover[i]<<' '<<segment[i]<<endl;
	cout<<endl;
	del(1,3,5);
	for(i=1;i<=t;i++)
		cout<<b[i]<<' '<<e[i]<<' '<<count[i]<<' '<<len[i]<<' '<<leftcover[i]<<' '<<rightcover[i]<<' '<<segment[i]<<endl;
}*/


int main()
{
	int i;
	cin>>num;
	for(i=0;i<num;i++)
	{
		cin>>x1>>y1>>x2>>y2;
		vertical[i+i].start=y1;vertical[i+i].end=y2;vertical[i+i].pos=x1;vertical[i+i].tag=true;
		vertical[i+i+1].start=y1;vertical[i+i+1].end=y2;vertical[i+i+1].pos=x2;vertical[i+i+1].tag=false;
		temp[i+i]=y1;temp[i+i+1]=y2;
	}
	qsort(vertical,num+num,sizeof(rect),cmp);
	qsort(temp,num+num,sizeof(int),cmpint);
	/*for(i=0;i<num+num;i++)
		cout<<vertical[i].pos<<' ';
	cout<<endl;*/
	top=0;
	index[top++]=temp[0];	
	for(i=1;i<num+num;i++)
		if(temp[i]!=temp[i-1])
			index[top++]=temp[i];
	/*for(i=0;i<top;i++)
		cout<<index[i]<<' ';
	cout<<endl;*/
	t=0;
	build(1,top);
	peri=0;pre=0;
	//cout<<top<<endl;
	for(i=0;i<num+num-1;i++)
	{
	
		left=lookup(vertical[i].start);
		right=lookup(vertical[i].end);
		if(vertical[i].tag)
		{
			insert(1,left,right);
		}
		else
		{
			del(1,left,right);
		}
		//cout<<vertical[i].tag<<' '<<left<<' '<<right<<endl;
		
		//if(i==0)
		//for(int j=1;j<=t;j++)
		//cout<<b[j]<<' '<<e[j]<<' '<<count[j]<<' '<<len[j]<<' '<<leftcover[j]<<' '<<rightcover[j]<<' '<<segment[j]<<endl;
		//cout<<vertical[i+1].pos-vertical[i].pos<<' '<<count[1]<<' '<<segment[1]<<' '<<len[1]<<' '<<pre<<endl;
		peri+=2*(vertical[i+1].pos-vertical[i].pos)*segment[1];
		if(len[1]>=pre)
			peri+=(len[1]-pre);
		else 
			peri-=(len[1]-pre);
		pre=len[1];
		//cout<<peri<<endl;
		
	}
	left=lookup(vertical[i].start);
	right=lookup(vertical[i].end);
	del(1,left,right);
	if(len[1]>=pre)
		peri+=(len[1]-pre);
	else 
		peri-=(len[1]-pre);
	cout<<peri<<endl;
	
}