哈喽大家好，我是 doooge，今天来点大家想看的东西啊
前置知识：
线段树，离散化，没了
1. 扫描线的步骤
例题：
有 \(n\) 个矩阵，每个矩阵的下表为 \(x_i\)，\(y_i\)，\(x2_i\)，\(y2_i\)，求这些矩阵的面积并。
\(n\le10^4\)，\(x_i,x2_i,y_i,y2_i\le 10^9\)。
暴力做法就不多说了，我们直接来讲扫描线
我们先拿个例子（横轴为 \(y\)，纵轴为 \(x\)）
扫描线的步骤是按照横轴/纵轴上的边，把这个图片分割成几个矩形：
我们从下往上开始扫，每次碰到横边就停下来，与上一次找到的横边连成一个矩阵，就像这样：
显然，我们计算的答案只与横边的在 \(y\) 轴的坐标有关
那我们需要怎样才能知道哪些地方有面积，哪些地方是空的呢？
我们需要分别讨论对于每个矩阵的下边和上边，我们可以给这些矩阵赋个边权，具体来说，我们给下边赋上 \(-1\)，上边赋上 \(1\) 来区分：
我们首先给横边按 \(x\) 来排序，这样能保证在遍历过程中的权值和一定 \(>0\)，扫描线所截的长度一定不是非负的了。
但是，如果有两条线段相交，中间的地方重合了，此时相交的部分我们只能算一遍，那我们该怎么办呢？
于是，离散化出场了！
我们把 \(y\) 轴离散化，把它们都丢尽一个数组里面，在进行去重，于是离散化完了这些点后，我们就可以将相邻的一条点建边就行了
因为我们建出来的新线段都是连续的，所以可以用线段树来维护这些小区间
那我们线段树该维护什么呢？这个其实不难：
- 这个区间的左，右坐标
- 这个区间实际上覆盖了的坐标
- 这个区间被多少个矩阵包含
于是这道题就变成了一道维护区间的题目，有扫描线扫到的线数次修改，每次修改一个区间（矩阵上面的一条横边）\(+1\) 或者 \(-1\)，要你计算此时扫描线包含的线段长度 \(\times\) 这条线与下一条线相差的高度
我们来试着模拟一下：
2. 扫描线的代码
2.1 线段树部分
先从定义节点开始，这个前面说过了，值得一提的是，因为只有点数 \(-1\) 条边，所以 \(l\) 到 \(r\) 表示的是 \(a_l\) 到 \(a_{r+1}\) 的区间：
struct Node{//线段树节点 int l,r,sum,cnt;//l和r表示t[i]维护a[l]到a[r+1]（注意，是+1！看了完整代码你就知道为什么了）的区间 //sum表示目前这个区间包含的线段的长度 //cnt表示目前有多少个矩阵完全包含这个线段
}t[8000010];//2n个点再加上四倍空间就是8倍空间
pushup 也不难写，注意这个判断覆盖可写可不写，具体要看你的 update 咋写的：
void pushup(int x){if(t[x].cnt){//这个线段被覆盖过 t[x].sum=a[t[x].r+1]-a[t[x].l];//因为a[r+1]-a[l]的长度才是a[l]到a[r]的长度}else{t[x].sum=t[ls(x)].sum+t[rs(x)].sum;}return;
}
update 跟正常的 update 差不多，但是如果你是用判 mid 的写法的话，注意要判断 \([l,r]\) 可能不在当前的区间的情况：
void update(int l,int r,int fa,int val){//l,r表示询问的区间if(a[t[fa].r+1]<=l||a[t[fa].l]>=r)return;//剪枝 if(a[t[fa].l]>=l&&a[t[fa].r+1]<=r){t[fa].cnt+=val;pushup(fa);//小细节，直接pushup来更新长度当然你也可以直接把pushup给搬过来 return;}update(l,r,ls(fa),val);//由于我们有剪枝，就不用判断了 update(l,r,rs(fa),val);pushup(fa);//别忘了pushup啊qwq return;
}
完整代码：
#include<bits/stdc++.h>
#define int long long//十年OI一场空，_______
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
using namespace std;
int a[200010],n,ans;//离散化数组
struct line{//线段 int l,r,h,w;//左长度，右长度和此时的高，以及他的权值 bool operator<(const line &a)const{return h<a.h;//从低到高排序 }
}line[200010];//2n条线段
struct Node{//线段树节点 int l,r,sum,cnt;//l和r表示t[i]维护a[l]到a[r+1]的区间 //sum表示目前这个区间包含的线段的长度 //cnt表示目前有多少个矩阵完全包含这个线段
}t[8000010];//2n个点再加上四倍空间就是8倍空间
void pushup(int x){if(t[x].cnt){//这个线段被覆盖过 t[x].sum=a[t[x].r+1]-a[t[x].l];//因为a[r+1]-a[l]的长度才是a[l]到a[r]的长度}else{t[x].sum=t[ls(x)].sum+t[rs(x)].sum;}return;
}
void build(int l,int r,int fa){//fa就是下标，个人习惯见谅 t[fa].r=r,t[fa].l=l,t[fa].sum=0,t[fa].cnt=0; if(l==r){return;}int mid=(l+r)>>1;build(l,mid,ls(fa));build(mid+1,r,rs(fa));return;
}
void update(int l,int r,int fa,int val){//l,r表示询问的区间if(a[t[fa].r+1]<=l||a[t[fa].l]>=r)return;//剪枝 if(a[t[fa].l]>=l&&a[t[fa].r+1]<=r){t[fa].cnt+=val;pushup(fa);//小细节，直接pushup来更新长度当然你也可以直接把pushup给搬过来 return;}update(l,r,ls(fa),val);//由于我们有剪枝，就不用判断了 update(l,r,rs(fa),val);pushup(fa);//别忘了pushup啊qwq return;
}
signed main(){cin>>n;for(int i=1;i<=n;i++){int x,y,x2,y2;//定义y1过不了编译，我也不知道为什么 cin>>x>>y>>x2>>y2;if(x>x2)swap(x,x2);if(y>y2)swap(y,y2);//必须保证x<x2，y<y2line[(i<<1)-1]={y,y2,x,1};//下边line[i<<1]={y,y2,x2,-1};//上边a[(i<<1)-1]=y,a[i<<1]=y2;}n<<=1;//线段数是矩阵数的两倍 sort(line+1,line+n+1);sort(a+1,a+n+1); int cnt=unique(a+1,a+n+1)-a-1;build(1,cnt-1,1);//注意cnt需要-1，因为cnt的点的数量for(int i=1;i<n;i++){//最后一条边就不用更新了update(line[i].l,line[i].r,1,line[i].w);//更新ans+=t[1].sum*(line[i+1].h-line[i].h);//计算答案 } cout<<ans<<endl;return 0;
}//完结撒花！！！
3.闲话
我这篇文章只写了扫描线的很小一部分分支，下一篇文章大概就是扫描线求区间边长的方法等等。
蒟蒻不才，膜拜大佬，如果有任何错字等问题，请在评论区提醒我。