扫描线

第一次听到扫描线这个东西时，感觉好神仙。
那是在小学。
现在初三了，我连后缀自动机都弄懂了，就是不懂扫描线。
网上关于扫描线的博客似乎不多，并且不是很适合我……
所以现在才懂了扫描线……
还是我太弱了啊……

扫描线大体思想

一个经典模型：现在给你一个坐标系，上面有许多矩形（这些矩形的长宽与坐标轴平行），求这些矩形并的面积。
很显然，难点在于矩形之间重复的面积。
直接暴力容斥？
不存在的。
这时我们就要用到扫描线。
可以把扫描线想象成，一条假想的线从坐标系的一端扫到另一边，然后计算出矩形并的面积。

扫描线的一般做法

假如这条线是从左到右扫。
对于每个矩形，我们可以将其拆成左边和右边的两条线段。
当扫描线经过左边时，扫面线上维护的值增加；当扫描线经过右边时，扫描线上维护的值减少。
可以用一棵线段树维护。
统计答案时，直接将扫描线上被覆盖的长度乘上这条线段与上一条线段之间的距离，累加起来就是答案。

重点

其它的都很简单，最难的是如何用线段树维护这个东西。
因为我们要去重，相当于扫描线上，被覆盖多次的线段都只能算一次。
对于线段树的每个节点，我们定义两个变量$cnt$和$len$，分别表示标记和线段内被覆盖的长度。
如果$cnt > 0$，则表示这整段区间被覆盖了，此时的$len$即为整个区间的长度。
如果$cnt=0$，那么$len=len_{leftchild}+len_{rightchild}$
这样子就可以维护了……
其中，标记可以不下传。
为什么呢？
因为对于每个矩形，必须先是左边加，然后右边减，并且两次在线段树上覆盖的节点都是相同的。
所以不可能出现某个节点有标记覆盖，但实际上它的儿子区间并没有满的情形。
其实，下传标记也可以（这样或许不局限于扫描线）

---

代码

未经验证
因为实在找不到合适的例题

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100000
#define MAXY 1000000000
int n;
struct Op{
	int x,y1,y2,ty;
} o[MAXN*2+1];
int m;
bool cmp(const Op &a,const Op &b){
	return a.x<b.x;
}
struct Node{
	int l,r;
	int cnt,len;
} d[MAXN*30];
int cnt=1;
void update(int,int,int);
void change(int,int,int,int,int,int);
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;++i){
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		o[++m]={x1,y1,y2,1};
		o[++m]={x2,y1,y2,-1};
	}
	sort(o+1,o+m+1,cmp);
	o[0].x=o[1].x;
	long long ans=0;
	for (int i=1;i<=m;++i){
		ans+=d[1].len*(o[i].x-o[i-1].x);//乘上这次和上一次的距离，统计答案
		change(1,1,MAXY,o[i].y1+1,o[i].y2,o[i].ty);//线段树的每个节点存的是一个由线段组成的区间，要将端点表示转化为线段表示
	}
	printf("%lld
",ans);
	return 0;
}
void update(int k,int l,int r){
	if (d[k].cnt)
		d[k].len=r-l+1;
	else
		d[k].len=d[d[k].l].len+d[d[k].r].len;
}
void change(int k,int l,int r,int st,int en,int c){
	if (st<=l && r<=en){
		d[k].cnt+=c;
		update(k,l,r);
		return;
	}
	int mid=l+r>>1;
	if (st<=mid){
		if (!d[k].l)
			d[k].l=++cnt;
		change(d[k].l,l,mid,st,en,c);
	}
	if (mid<en){
		if (!d[k].r)
			d[k].r=++cnt;
		change(d[k].r,mid+1,r,st,en,c);
	}
	update(k,l,r);
}