扫描线
扫描线法是一种求矩形面积并/周长并的好方法。
扫描线：假设有一条扫描线从一个图形的下方扫向上方（或者左方扫到右方），那么通过分析扫描线被图形截得的线段就能获得所要的结果。该过程可以用线段树进行加速。
面积的求法其实可以简化为
∑
\sum
∑
截线段长度
×
\times
×
扫过的高度。这也是扫描线算法最基础的应用。
问题在于如何才能模拟扫描线从下向上扫过图形，并且快速计算出当前扫描线被截得的长度。
现在假设，
扫描线每次会在碰到横边的时候停下来
（基本思路），如图。
简单来说，可对图形面积产生影响的元素，也就是这些横边左右端点的坐标。
为了快速计算出截线段长度，可以将横边赋上不同的权值，具体为：
对于一个矩形，其下边权值为
1
1
1
，上边权值为
−
1
-1
−
1
。
然后把所有的横边按照
y
y
y
坐标升序排序。这样，对于每个矩形，扫描线总是会先碰到下边，然后再碰到上边。那么就能保证扫描线所截的长度永远非负了。
这样操作以后，就可以和线段树扯上关系。先把所有端点在
x
x
x
轴上离散化（其实就是把所有点的横坐标存到
X
[
]
X[]
X
[
]
里，然后升序排个序，最后去重）。
在这个例子中，四个端点的纵投影总共把x轴切割成了五个部分。取中间的三部分线段，建立一棵线段树，线段树上每个点位维护一条线段（也就是一个区间）的信息：
1.该线段被覆盖了多少次（被多少个矩形所覆盖）。
2.该线段内被整个图形所截的长度是多少。
显然，只要一条线段被覆盖，那么它肯定被图形所截。所以，整个问题就转化为了一个区间查询问题，即：每次将
当前扫描线扫到的边
对应的信息 按照
之前赋上的权值
更新，然后
再查询线段树根节点的信息
，
最后得到当前扫描线扫过的面积
。这就可以用线段树来实现了（毕竟人家叫“线段”树嘛）。
下面我们来直观感受一下这个过程，图中绿色部分表示已计算的面积。
我们已经知道，这棵线段树的每个节点都对应了一条线段。考虑将线段树上节点对应的区间和横边建立映射关系。先看对于一个叶子节点
p
p
p
，建树时保证了
t
r
e
e
[
p
]
.
l
=
t
r
e
e
[
p
]
.
r
tree[p].l=tree[p].r
t
ree
[
p
]
.
l
=
t
ree
[
p
]
.
r
，但其保存的信息很显然不可能只是某条线段的一个端点。
（如果一条线段的两个端点重合，那么它实质上仅是一个点）
。再看一个节点的左右儿子，同样地，建树的时候已经保证了左右儿子的区间不会重合（交集为空），但是看这样两条相邻线段：
[
1
,
2
]
,
[
2
,
3
]
[1,2],[2,3]
[
1
,
2
]
,
[
2
,
3
]
你会发现
[
1
,
2
]
∩
[
2
,
3
]
=
2
[1,2]\cap[2,3]={2}
[
1
,
2
]
∩
[
2
,
3
]
=
2
，也就是说左儿子的右端点和右儿子的左端点其实是重合的。
考虑把线段树每个节点
p
p
p
对应的区间
(
t
r
e
e
[
p
]
.
l
,
t
r
e
e
[
p
]
.
r
)
(tree[p].l,tree[p].r)
(
t
ree
[
p
]
.
l
,
t
ree
[
p
]
.
r
)
不变，改变区间和横边的映射关系，具体为：节点
p
p
p
对应
X
[
t
r
e
e
[
p
]
.
l
]
,
X
[
t
r
e
e
[
p
]
.
r
+
1
]
X[tree[p].l],X[tree[p].r+1]
X
[
t
ree
[
p
]
.
l
]
,
X
[
t
ree
[
p
]
.
r
+
1
]
这条横边。可以看到，这里很机智地把右端点的对应关系给改了下，于是就兼容了。
代码：
#include<bits/stdc++.h>
#define in read()
#define MAXN 1000500
#define lson (p<<1)
#define rson (p<<1|1)
#define int long long
using namespace std;
struct SegmentTree{
int l,r,sum,len;
}t[MAXN<<2];
struct ScanLine{
int l,r,h;
int mark;
bool operator < (const ScanLine &rhs) const {
return h<rhs.h;
}
}L[MAXN<<1];
int n,X[MAXN<<1],ans=0;
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*f;
}
void pushup(int p) {
int l=t[p].l,r=t[p].r;
if(t[p].sum)t[p].len=X[r+1]-X[l]; /* 也就是说被覆盖过 */
else t[p].len=t[lson].len+t[rson].len;
}
void update(int p,int ll,int rr,int mark){
int l=t[p].l,r=t[p].r,mid=(l+r)/2;
if(X[r+1]<=ll or rr<=X[l])return;
if(ll<=X[l] and X[r+1]<=rr){
t[p].sum+=mark;
pushup(p);
return;
}
update(lson,ll,rr,mark);
update(rson,ll,rr,mark);
pushup(p);
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r)return;
int mid=(l+r)/2;
build(lson,l,mid);
build(rson,mid+1,r);
return;
}
signed main(){
n=in;
for(int i=1;i<=n;i++){
int a=in,b=in,c=in,d=in;
X[2*i-1]=a,X[2*i]=c;
L[2*i-1]=(ScanLine){a,c,b,1};
L[2*i]=(ScanLine){a,c,d,-1};
}
n<<=1;
sort(X+1,X+n+1);
sort(L+1,L+n+1);
int tot=unique(X+1,X+n+1)-X-1;
build(1,1,tot-1);
for(int i=1;i<n;i++){
update(1,L[i].l,L[i].r,L[i].mark);
ans+=t[1].len*(L[i+1].h-L[i].h);
}
cout<<ans<<'\n';
return 0;
}