——引例
有时候我们会碰见一些求n个矩形的面积并（就是说n个矩形，每两个矩形之间都有可能重叠，然后问你这n个矩形的总占地面积为多少），或者周长并（就是说n个矩形拼成的最外围轮廓的周长和）
对于这种问题，在最初的做题中用的都是线段树+离散化去维护区间去求解最后的面积并或者周长并，但是在后面就有了本篇讲述的扫描线算法
不论是线段树+离散化，还是扫描线算法，其算法的时间复杂度都为O(N*logN)
扫描线算法主要倾向于线段树+离散化这类思想，然后扫描求解过程有点像积分，那么我们开始讲解扫描线。
问题+解决思路
P5490 【模板】扫描线
这题其实我当时没写，我写的是另一道，但是由于都是一个板子改一下数据即可，那么现在开始来进行扫描线算法的分析和应用
分析扫描线
扫描线：假设有一条扫描线从一个图形的下方扫向上方（或者左方扫到右方），那么通过分析扫描线被图形截得的线段就能获得所要的结果。该过程可以用线段树进行加速。
对于1的图就是这样，每次扫描线只有碰到矩形的边界才会停止，恰好将图形分成2*n-1个区域
对于2来说，很显而易见，如果我们矩形的上下边界高度存储起来的话，那么我们每个区块的高度，其实就是y[i+1]-y[i]
对于3来说，区块的长度就是矩形那条线的最长的长度，首先就是对于高度是1的长度为（20~80），对于3高度的长度（10~80），对于5和6的长度，很明显的都是(10~90)
对于4来说，当前区块的面积并就为高度*当前区块的长度
解释一下5，区块的长度可以用线段树来维护， 每当标记结点cnt!=0的时候，说明被覆盖了，直接加上区间值即可，别的都是左子树长度+右子树长度
细节
计算时右坐标右偏移一位，传参时右坐标左偏移一位
我们现在开始来说明为什么会有这样的结论
我们先来写出X坐标离散化后的一个表
按照我们上面这个图我们可以建出一棵树
结合上面那个表，我们发现如果真的按照上面的表来算横坐标的话，那么对于4,5这两个节点，一个是10~20，另一个是30~30这样很明显是不对的中间有长达10的空挡，并且我们的线段树节点要保存的不是一个点，而是一条线段，所以我们的右端点在计算的时候要进行右偏移一位
就好比我们有一个扫描线，扫描到的是10~50,我们要存储1~4吗？不是的，因为我们在计算的时候右端点会向右偏移一位，所以我们此时在存储右端点的时候要将右端点向左偏移一位
分析所需要用到的函数和变量
扫描线的结构体 ：
struct line{
int x1,x2;//扫描线的左边界和右边界
int y;//扫描线所处的高度，也就是y
int tag;//判断是下边还是上边，下边+贡献，下边-贡献
}L[10086];线段树节点的结构体：
struct node{
int l;//表示节点覆盖的左端点
int r;//节点覆盖的右端点
int len;//表示长度
int cnt;//表示是否被覆盖的标志
}tree[10086];建树的函数：
void build(int i,int l,int r)
{
tree[i].l=l,tree[i].r=r;
if(l==r)
{
return;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
return ;
}回退计算最终覆盖长度的函数
void push_up(int i)
{
if(tree[i].cnt!=0)//有覆盖标记直接计算
{
tree[i].len=X[tree[i].r+1]-X[tree[i].l];
}
else//没有覆盖标记计算左子树和右子树的结点之和
{
tree[i].len=tree[i*2].len+tree[i*2+1].len;
}
return ;
}扫描线扫描过程中遇到的边界的线段和
void add(int i,int l,int r,int tag)
{
if(l>tree[i].r||tree[i].l>r)
{
return ;
}
if(tree[i].l>=l&&tree[i].r<=r)
{
tree[i].cnt+=tag;
push_up(i);
return ;
}
add(i*2,l,r,tag);
add(i*2+1,l,r,tag);
push_up(i);
return ;
}扫描线板子完整代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a,b,c,d;
struct line{
int x1,x2;
int y;
int tag;
}L[10086];
struct node{
int l;
int r;
int len;//表示长度
int cnt;//表示是否被覆盖的标志
}tree[10086];
int X[10086];
bool cmp(line x,line y)
{
return x.y<y.y;
}
void push_up(int i)
{
if(tree[i].cnt!=0)
{
tree[i].len=X[tree[i].r+1]-X[tree[i].l];
}
else
{
tree[i].len=tree[i*2].len+tree[i*2+1].len;
}
return ;
}
void build(int i,int l,int r)
{
tree[i].l=l,tree[i].r=r;
if(l==r)
{
return;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
return ;
}
void add(int i,int l,int r,int tag)
{
if(l>tree[i].r||tree[i].l>r)
{
return ;
}
if(tree[i].l>=l&&tree[i].r<=r)
{
tree[i].cnt+=tag;
push_up(i);
return ;
}
add(i*2,l,r,tag);
add(i*2+1,l,r,tag);
push_up(i);
return ;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a>>b>>c>>d;
L[i]={a,c,b,-1};
L[i+n]={a,c,d,1};
X[i]=a;
X[i+n]=c;
}
sort(L+1,L+1+2*n,cmp);
sort(X+1,X+1+2*n);
int len=unique(X+1,X+1+2*n)-X-1;
build(1,1,len-1);
int ans=0;
for(int i=1;i<2*n;i++)
{
int l=lower_bound(X+1,X+1+len,L[i].x1)-X;
int r=lower_bound(X+1,X+1+len,L[i].x2)-X;
add(1,l,r-1,L[i].tag);
ans+=tree[1].len*(L[i+1].y-L[i].y);
}
cout<<ans;
return 0;
}例题：
由于这种问题都是一种板子，所以下面的例题也就不放代码了，当然了只是对于面积并来说，还有一种周长并，日后更新切莫着急
P1884 [USACO12FEB] Overplanting S
我感觉俩题都没啥区别，但是上面是个蓝，下面是个绿，没看懂。
各位看官老爷再见
