线段树的样例程序

				//*线段树样例*//
				#include 
				#include 
				#include 
				#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].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].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					{
						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					{
						if(temp[i] != index[counter-1])
						{
							index[counter++]=temp[i];
						}
					}
				
					t=0;
					Build(1,counter);
					C= pre=0;
					for(i=0;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;
				}