http://acm.pku.edu.cn/JudgeOnline/problem?id=1177


#include
<iostream>
#include
<algorithm>
#define MAXN 10005
using namespace std;

struct segment
{
 
int L,R;
 
int len,linenum,cover; 
 
// 以当前区间为根的树被覆盖的区间的总长度,
 
// 以当前区间为根的树被覆盖的区间数目,当前区间被覆盖的次数,
 bool lcover,rcover;
}
;

struct line
{
 
//int start,end;//离散化之后竖边的两个Y值
 int x;
 
int flag;//记录左右边
 bool operator<const line &a )
 
{
  
return x<a.x;
 }

}
;

struct point
{
 
int y;
 
int num;
 
bool operator<const point & a )
 
{
  
return y<a.y;
 }

}
;

segment tree[MAXN
*4];
line yline[MAXN];
point Ypoint[MAXN];
point Xpoint[MAXN];
int Xpost[MAXN][2];
int Ypost[MAXN][2];

void make_tree( int v, int l, int r )
{
 
int mid;
 tree[v].L
=l; tree[v].R=r;
 tree[v].linenum
=tree[v].len=0;
 tree[v].lcover
=tree[v].rcover=false;
 
if( r-l>1 )
 
{
  mid
=(l+r)>>1;
  make_tree( v
<<1, l, mid );
  make_tree( (v
<<1)+1, mid, r );
 }

}


void getline( int v ) // 获得以当前接点为根的树被覆盖的区间总长度
{
 
if( tree[v].cover>0 )tree[v].len=Ypoint[tree[v].R].y-Ypoint[tree[v].L].y;
 
else if( tree[v].R-tree[v].L==1 )tree[v].len=0;
 
else tree[v].len=tree[v<<1].len+tree[(v<<1)+1].len;
}


void getlinenum( int v ) //获得以当前节点为树根的子树被覆盖区间的总数
{
 
if( tree[v].cover>0 )
  tree[v].lcover
=tree[v].rcover=true,tree[v].linenum=1;
 
else if( tree[v].R-tree[v].L==1 )
  tree[v].lcover
=tree[v].rcover=false,tree[v].linenum=0;
 
else  
 
{
  tree[v].lcover
=tree[v<<1].lcover;
  tree[v].rcover
=tree[(v<<1)+1].rcover;
  tree[v].linenum
=tree[v<<1].linenum+tree[(v<<1)+1].linenum-tree[v<<1].rcover*tree[(v<<1)+1].lcover;
 }

}


void update( int v, int l, int r, int flag )
{
 
int mid;
 
if( tree[v].L==&& tree[v].R==r )
 
{
  tree[v].cover
+=flag;
  getline( v );
  getlinenum( v );
  
return ;
 }

 mid
=(tree[v].L+tree[v].R)>>1;
 
if( r<=mid )update( v<<1, l, r, flag );
 
else if( l>=mid )update( (v<<1)+1, l, r, flag );
 
else 
 
{
  update( v
<<1, l, mid, flag );
  update( (v
<<1)+1, mid, r, flag );
 }

 getline( v );
 getlinenum( v );
}


int main( )
{
 
int n,i,t1,t2;
 
int x1,x2,y1,y2;
 
while( scanf("%d",&n) != EOF )
 
{
  
for( i=0; i<n; i++ )
  
{
   scanf(
"%d%d%d%d",&x1,&y1,&x2,&y2);
   t1
=i<<1;t2=(i<<1)+1;
   Xpoint[t1].y
=x1;Xpoint[t2].y=x2;
   Xpoint[t1].num
=-(i+1);
   Xpoint[t2].num
=i+1;
   Ypoint[t1].y
=y1;Ypoint[t2].y=y2;
   Ypoint[t1].num
=-(i+1);  //竖边下面的点
   Ypoint[t2].num=i+1;     //竖边上面的点
   yline[t1].x=x1;yline[t2].x=x2;
   yline[t1].flag
=1;//负号矩形左边
   yline[t2].flag=-1;//正号矩形右边
  }

  sort( yline, yline
+(n<<1) );
  sort( Xpoint, Xpoint
+(n<<1) );
  sort( Ypoint, Ypoint
+(n<<1) );
  
for( i=0; i<(n<<1); i++ )
  
{
   
if( Xpoint[i].num<0 )Xpost[-Xpoint[i].num-1][0]=i;
   
else Xpost[Xpoint[i].num-1][1]=i;
  }

  
for( i=0; i<(n<<1); i++ )
  
{
   
if( Ypoint[i].num<0 )
    Ypost[Xpost[
-Ypoint[i].num-1][0]][0]=Ypost[Xpost[-Ypoint[i].num-1][1]][0]=i;
   
else Ypost[Xpost[Ypoint[i].num-1][0]][1]=Ypost[Xpost[Ypoint[i].num-1][1]][1]=i;
  }

  make_tree( 
10, (n<<1)-1 );
  
int ans=0,Len=0;
  update( 
1, Ypost[0][0], Ypost[0][1], yline[0].flag );
  
for( i=1; i<2*n; i++ )
  
{
   ans
+=2*tree[1].linenum*(yline[i].x-yline[i-1].x);
   ans
+=abs(tree[1].len-Len);
   Len
=tree[1].len;
   update( 
1, Ypost[i][0], Ypost[i][1], yline[i].flag );
  }

  ans
+=abs(tree[1].len-Len);
  printf(
"%d\n",ans);
 }

 
return 0;
}