Description
在一个平面上放置一些矩形，所有的边都为垂直或水平。每个矩形可以被其它矩形部分或完全遮盖，所有矩形合并成区域的边界周长称为轮廓周长。
要求：计算轮廓周长。
数据规模：
0≤矩形数目<5000；
坐标数值为整数，范围是[-10000，10000]。
Input
第一横列是墙上所贴的长方形总数。之后每一横列是一个长方形的左下角与右上角的整数坐标。个各坐标的x值在前，y值在后。
Output
应有一非负整数，即为长方形覆盖图形的总周长
Sample Input
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
Sample Output
228
线段树+扫描线，参考[Baltic 2001]Mars Maps
不过还是要讲一个东西，关于排列方式的问题。
排序的时候，在同一位置的起始边需要在终止边之前枚举
为什么？
首先本题统计答案的时候，应该是计算每次操作后，添加或删除的区间大小。
然后扫描线从两个方向扫描一下即可。
那么如果我们将终止边排在起始边之前的话，两条线之间必然会有因为时间差而导致的空隙，也就是程序实现的时候，先加了终止边，又加了起始边，等于是把这条边算了两次，但是实际是不能算的！！！
所以说我们在排序的时候，要将起始边排在终止边的前面，这样就不会出现多加的问题了。
(ps：这个代码是我很久之前写的，所以和上一题的码风可能有所区别）
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e4;
int tree[N*10+100],cnt[N*10+100];
int ans;
int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*f;
}
struct AC{
int val,first,last,cnt;
};
bool cmp(AC x,AC y){
if (x.val<y.val) return 1;
if (x.val==y.val) if (x.cnt>y.cnt) return 1;
return 0;
}
void updata(int p){
if (cnt[p]){
if (tree[p]!=-1) tree[p]+=cnt[p];
cnt[p*2]+=cnt[p];
cnt[p*2+1]+=cnt[p];
cnt[p]=0;
}
}
void change(int p,int l,int r,int x,int y,int t){
if (x<=l&&r<=y&&tree[p]!=-1){
if ((tree[p]==1&&t==-1)||(tree[p]==0&&t==1)) ans+=r-l;
tree[p]+=t; cnt[p*2]+=t; cnt[p*2+1]+=t;
return;
}
int mid=(l+r)>>1;
updata(p*2);updata(p*2+1);
if (x<mid) change(p*2,l,mid,x,y,t);
if (y>mid) change(p*2+1,mid,r,x,y,t);
if (tree[p*2]==tree[p*2+1]) tree[p]=tree[p*2];
else tree[p]=-1;
}
AC h[N+100],s[N+100];
int main(){
int n=read();
for (int i=1;i<=n;i++){
int a=read(),b=read(),c=read(),d=read();
h[i].cnt=-1; h[n+i].cnt=1;
s[i].cnt=1; s[n+i].cnt=-1;
h[i].val=d; h[i].first=a; h[i].last=c;
h[i+n].val=b; h[i+n].first=a; h[i+n].last=c;
s[i].val=a; s[i].first=b; s[i].last=d;
s[i+n].val=c; s[i+n].first=b; s[i+n].last=d;
}
sort(h+1,h+2*n+1,cmp);
sort(s+1,s+2*n+1,cmp);
ans=0;
for (int i=1;i<=n*2;i++)
change(1,-N,N,h[i].first,h[i].last,h[i].cnt);
for (int i=1;i<=n*2;i++)
change(1,-N,N,s[i].first,s[i].last,s[i].cnt);
printf("%d
",ans);
return 0;
}