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==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( 1, 0, (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;
}