思路：
以y的值进行离散化
根据x的值 对每一条y轴边进行处理，如果是"左边"则插入，是"右边"则删除。
/*
扫描线+线段树+离散化
求多个矩形的周长
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
using namespace std;
const int maxn = ;
const int maxm = ;
struct SegTree{
int l,r;
int len;//区间代表的长度
int segnum;//区间被分成的段数
int cover;//区间被覆盖的次数
int sum;//区间被覆盖的总长度
bool lcover,rcover;
}ST[ maxm<< ];
struct Line{
int st,ed,x;//竖边的两个y值
bool InOut;//是否为左边
bool operator < (Line L) const{
return x<L.x;
}
}; Line yLine[ maxm ];
int yIndex[ maxm ];
int n; void build( int L,int R,int n ){
ST[ n ].l = L;
ST[ n ].r = R;
ST[ n ].len = yIndex[ R ]-yIndex[ L ];
ST[ n ].sum = ST[ n ].cover = ST[ n ].segnum = ;
ST[ n ].lcover = ST[ n ].rcover = false;
if( R-L> ){
int mid = (L+R)/;
build( L,mid,*n );
build( mid,R,*n+ );
}
return ;
} void Update_Len( int n ){
if( ST[n].cover> ){
ST[n].sum = ST[n].len;
}
else if( ST[n].r-ST[n].l> ){
ST[n].sum = ST[*n].sum+ST[*n+].sum;
}
else
ST[n].sum = ;
} void Update_Segnum( int n ){
if( ST[n].cover> ){
ST[n].lcover = ST[n].rcover = true;
ST[n].segnum = ;
}
else if( ST[n].r-ST[n].l> ){
ST[n].lcover = ST[*n].lcover;
ST[n].rcover = ST[*n+].rcover;
ST[n].segnum = ST[*n].segnum+ST[*n+].segnum-ST[*n].rcover*ST[*n+].lcover;
}
else{
ST[n].segnum = ;
ST[n].lcover = ST[n].rcover = false;
}
} void PushUp ( int n ){
Update_Len( n );//求节点包含的线段总长度
Update_Segnum( n );
} void Insert( int left,int right,int n ){
if( ST[ n ].l==left&&ST[ n ].r==right ){
ST[ n ].cover++;
}
else {
int mid = (ST[ n ].l+ST[ n ].r)/;
if( right<=mid )
Insert( left,right,*n );
else if( left>=mid )
Insert( left,right,*n+ );
else{
Insert( left,mid,*n );
Insert( mid,right,*n+ );
}
}
PushUp( n );
} void Delete( int left,int right,int n ){//删除矩形的右边
if( ST[ n ].l==left&&ST[ n ].r==right ){
ST[ n ].cover--;
}
else {
int mid = (ST[ n ].l+ST[ n ].r)/;
if( right<=mid )
Delete( left,right,*n );
else if( left>=mid )
Delete( left,right,*n+ );
else{
Delete( left,mid,*n );
Delete( mid,right,*n+ );
}
}
PushUp( n );
} int GetIndex( int value ,int cnt ){
return lower_bound(yIndex,yIndex+cnt,value )-yIndex;
} int main(){
while( scanf("%d",&n)== ){
int cnt = ;
int x1,y1,x2,y2;
for( int i=;i<n;i++ ){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
yLine[ *i ].x = x1;
yLine[ *i+ ].x = x2;
yLine[ *i ].st = yLine[ *i+ ].st = y1;
yLine[ *i ].ed = yLine[ *i+ ].ed = y2;
yLine[ *i ].InOut = true;
yLine[ *i+ ].InOut = false;
yIndex[ *i ] = y1;
yIndex[ *i+ ] = y2;
}
sort( yIndex,yIndex+*n );
sort( yLine,yLine+*n );
for( int i=;i<*n;i++ ){
if( yIndex[i]!=yIndex[i-] )
yIndex[cnt++] = yIndex[i-];
}
yIndex[cnt++] = yIndex[*n-];
build( ,cnt-, );
int Ans = ;
int PreSum = ;;//上一次记录的长度
for( int i=;i<*n-;i++ ){
if( yLine[i].InOut ){
Insert( GetIndex(yLine[i].st,cnt),GetIndex(yLine[i].ed,cnt), );
}
else{
Delete( GetIndex(yLine[i].st,cnt),GetIndex(yLine[i].ed,cnt), );
}
Ans += ST[].segnum**(yLine[i+].x-yLine[i].x);
Ans += abs(ST[].sum-PreSum);
PreSum = ST[].sum;
}
Delete( GetIndex(yLine[*n-].st,cnt),GetIndex(yLine[*n-].ed,cnt), );
//特殊处理最后一条出边，因为没有下一条竖边了
Ans += abs(ST[].sum-PreSum);
printf("%d\n",Ans);
}
return ;
}