扫描线
思想
扫描线的思想十分简单，就是把矩形分为多次小的矩形求解罢了，关键在于实现
记得有一次周考就写挂了......
实现
首先想要正好不重不漏地扫过一个矩形（只有一个的情况下）而不影响其他非矩形地方的方法是什么？
假设我扫描线是从下往上扫的，那么对于这个矩形而言，我在遇到下边的时候权值+1,遇到上边时权值-1
为了保证左侧和右侧不会扫过头（不会扫过其宽度），那么我应该维护这个线段区间权值+1-1.
为了求解面积，我不可忽略这个矩形的高度，换句话说，这个状态应该是持续性的（扫描有过程），而持续的时间就是高度
而这种区间的维护我可以利用线段树完成
现在扩展到有重叠的多个矩形，发现如果+1这样的话，可能某些区间会达到2/3/4等等等等，但是面积我应该只计算1
所以我线段树中应该维护两个值：重叠次数和贡献
贡献只有0/1之分，而重叠次数可以有很多
当且仅当重叠次数=0时，贡献为0
差不多就行了吧，注意排序即可。
然后离散化的话，就需要一个映射关系
例如在线段树上节点x对应[X[tree[x].l],X[tree[x].r+1]]这条横边
代码：
#include <bits/stdc++.h>
//#define int long long
using namespace std;
struct xd{
long long l;
long long r;
long long hi;
long long lz;//表示上边或下边
}line[1000005];
struct node {
long long sum; //（被覆盖的次数
long long l;
long long r;
long long len;//表示长度（被截取后 ，即实际有效长度
} tree[4000005];
long long X[1000005];
void build(long long rt,long long l,long long r){
tree[rt].l=l;
tree[rt].r=r;
if(l==r){
return;
}
long long mid = (l + r) >> 1;
build(rt*2, l, mid);
build(rt*2+1, mid + 1, r);
return;
}
bool cmp(xd x,xd y){
if(x.hi!=y.hi)return x.hi<y.hi;
else return x.l<y.l;
}
void pushup(long long rt) {
int l = tree[rt].l, r = tree[rt].r;
if(tree[rt].sum)
tree[rt].len=X[r+1]-X[l];//实际长度 ，只要不为零，说明对整个面积有贡献，是被全部覆盖的
else
tree[rt].len=tree[rt*2].len+tree[rt*2+1].len;//可能存在被部分覆盖的情况，需要看儿子的贡献
}
void updata(int rt,long long L,long long R,long long c) {
int l=tree[rt].l;
int r=tree[rt].r;
if(X[r+1]<=L||R<= X[l])
return;
if(L<=X[l]&&X[r+1]<= R) {
tree[rt].sum+=c;
pushup(rt);
return;
}
updata(rt*2, L, R, c);
updata(rt*2+1, L, R, c);
pushup(rt);
}
int main() {
ios::sync_with_stdio(false);
long long n;
cin >> n;
for(long long i=1;i<=n;i++){
long long a,b,c,d;
cin >> a>> b>> c>> d;
X[i*2-1]=a;
X[i*2]=c;
line[i*2-1]=(xd){a,c,b,1};
line[i*2]=(xd){a,c,d,-1};
}
n<<=1;
sort(X+1,X+1+n);
sort(line+1,line+1+n,cmp);
int tot = unique(X + 1, X + n + 1) - X - 1;//去重，tot表示去重后的个数
//补充下，unique(a,b)-a表示找a-b的非重复个数，并更新去重的数组；(大概？
build(1,1,tot-1);//右边的没了
long long ans=0;
for(int i=1;i<n;i++){
updata(1,line[i].l,line[i].r,line[i].lz);
ans+=tree[1].len*(line[i + 1].hi-line[i].hi);
// cout<<ans<<endl;
}
cout<<ans;
}