AcWing 247. 亚特兰蒂斯
题意：给定若干个矩形（长宽均平行于坐标轴），求它们的面积并（矩形的顶点坐标可以是实数）。
本题是扫描线算法的模板题。
扫描线，顾名思义，就是按照一条线扫过去，对于本题
如上图，这就是扫描线的过程。
发现按照线扫描的话，每次我们只需要维护出非零的位置个数，然后乘上两条线之间的距离就可以了。
这个数据结构需要支持区间增/减1（减法保证在这之前有加法），还有根节点查询。
如果使用懒标记，麻烦无比，下面考虑不用懒标记的维护方法。
令 \(cnt\) 表示这个节点自己恰好被覆盖的次数（不考虑父节点、子节点的合并），\(sz\) 表示不考虑祖先的覆盖长度。
若当前节点有cnt，长度就是整个区间；否则从两个子节点相加；每次修改节点需要立即pushup。（注意需要判断叶子节点，否则会导致4n的位置访问8n的内存）。
关于扫描线 线段树不需要pushdown的理解：
因为他只是往下看的，还有一个cnt，只要祖先有cnt，他就无所谓是什么。
如果它的子节点更新了，若祖先没有了cnt，那它得到的子节点信息也一定是最新的。
注意cnt表示这个区间作为完整区间覆盖的次数（就是分裂出来覆盖的次数）。
注意这里维护出来的len是只考虑这个子树内的懒标记得出的（虽然可能是错的，反正只要祖先节点整体覆盖就行了，管他是什么）。
更新了一个位置，那么它的子节点因为不考虑父节点，肯定是对的，然后他自己也是对的，往上如果有cnt标记，无影响；否则从两个子节点+也是对的。（贡献会被累加）
然后因为下标不一定是整数，所以需要离散化，线段树维护的实际是 \([y_a,y_a+1]\) 的区间。
比如 \(1,1.2,1.3,1.9\)，对应成三个数 \([1,1.2],[1.2,1.3],[1.3,1.9]\)，建立线段树。
综上，可以 \(O(n\log n)\)。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<cstdlib>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l,i##end=r;i<i##end;++i)
#define Rs(i,l,r) for(int i=l,i##end=r;i>i##end;--i)
#define Le(i,l,r) for(int i=l,i##end=r;i<=i##end;++i)
#define Re(i,l,r) for(int i=l,i##end=r;i>=i##end;--i)
#define L(i,l) for(int i=0,i##end=l;i<i##end;++i)
#define E(i,l) for(int i=1,i##end=l;i<=i##end;++i)
#define W(t) while(t--)
#define Wh while
const int N=10010,M=2*N,K=4*M;
int n,len,cnt[K],l[K],r[K];
double x1[N],y1[N],x2[N],y2[N],ans,ls[M],sz[K];
struct seg{
double x;
int l,r,s;
bool operator<(const seg &A)const{
return x<A.x;
}
}s[M];
void pushup(int p){
if(cnt[p])sz[p]=ls[r[p]+1]-ls[l[p]];
else if(l[p]==r[p])sz[p]=0;
else sz[p]=sz[p<<1]+sz[p<<1|1];
}
void update(int p,int L,int R,int k){
if(L<=l[p]&&r[p]<=R){
cnt[p]+=k;
pushup(p);
return;
}
int mid=(l[p]+r[p])>>1;
if(L<=mid)update(p<<1,L,R,k);
if(R>mid)update(p<<1|1,L,R,k);
pushup(p);
}
void build(int p,int L,int R){
if(p>80080){
cout<<"SB";
exit(0);
}
l[p]=L,r[p]=R;
if(L==R)return;
int mid=(L+R)>>1;
build(p<<1,L,mid),build(p<<1|1,mid+1,R);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=0;
Wh(cin>>n,n){
ans=len=0;
++t;
E(i, n)cin>>x1[i]>>y1[i]>>x2[i]>>y2[i],ls[len++]=y1[i],ls[len++]=y2[i];
sort(ls,ls+len);
len=unique(ls,ls+len)-ls;
// L(i, len)cout<<ls[i]<<' ';
// cout<<'\n';
build(1,0,len-2);
int tot=0;
E(i, n){
int l=lower_bound(ls,ls+len,y1[i])-ls,r=lower_bound(ls,ls+len,y2[i])-ls;
s[tot++]={x1[i],l,r,1};
s[tot++]={x2[i],l,r,-1};
}
sort(s,s+tot);
L(i, tot){
if(i)ans+=(s[i].x-s[i-1].x)*sz[1];
// cout<<s[i-1].x<<' '<<s[i].x<<' '<<sz[1]<<'\n';
// cout<<s[i].l<<' '<<s[i].r-1<<'\n';
update(1,s[i].l,s[i].r-1,s[i].s);
}
cout<<"Test case #"<<t<<'\n';
cout<<fixed<<setprecision(2)<<"Total explored area: "<<ans<<"\n\n";
}
return 0;
}