AcWing 247. 亚特兰蒂斯

题意：给定若干个矩形（长宽均平行于坐标轴），求它们的面积并（矩形的顶点坐标可以是实数）。

本题是扫描线算法的模板题。

扫描线，顾名思义，就是按照一条线扫过去，对于本题

扫描线 - OI Wiki (oi-wiki.org)

如上图，这就是扫描线的过程。

发现按照线扫描的话，每次我们只需要维护出非零的位置个数，然后乘上两条线之间的距离就可以了。

这个数据结构需要支持区间增/减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;
}