【线段树专题】扫描线算法

_GeorgeAAAADHD_ · 2023-07-17 11:45:48 · 个人记录

扫描线，顾名思义，它可以解决矩形的面积并、周长并以及多边形面积等几何问题。

1. 矩形面积并

P5490 【模板】扫描线

如下图，假设我们要求 \text{A、B} 两矩形的总面积。

我们便可以将这两个矩形分成三个不重合的矩形。

)

此时 \text{矩形面积} = \text{宽} \times \text{高}。其中高只需要拿原来两个矩形的四个顶点依次相减即可。

那么求宽比较麻烦。我们在此引进一个概念：

入边，即一个矩形的下边；
出边，即一个矩形的上边。

如下图，原矩形（\text{图A}）的矩形 A 入边为 2 号边，出边为 4 号边。矩形 B 的入边为 1 号边，出边为 3 号边。

如上图，我们用 P_1,\ P_2,\ P_3 分别表示从左到右各线段的长度，则矩形 A, B, C 的宽分别为 P_1+P_2,\ P_1+P_2+P_3,\ P_2+P_3。

于是我们发现，诶，这不就是求序列 P 的区间和吗？自然想到线段树。定义标志 T_1,\ T_2,\ T_3，分别来判断 P_1,\ P_2,\ P_3 能否用来计算宽度。对于每一段 P_i，我们一直向上走，若遇到入边则 T_i 加 1，若遇到出边则 T_i 减 1。很明显，如果 T_i > 0，则在这一段高之间的 P_i 可以用来计算宽。

得到每条 P_i 的 T_i 以后，我们就能计算矩形 A,\ B,\ C 的宽了。

这种算法被称为 扫描线算法。上图中的边 1,\ 2,\ 3,\ 4 就是所谓的扫描线。用线段树维护每条扫描线，以便于进行区间求宽度和操作。

哦对了，写代码的时候还要先对 x 轴进行离散化，不然 x 轴过长可能会爆空间。

下面就是该例题的详细代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
int n,x1,x2,yy1,y2,sum=0,ans=0; //sum为扫描线数量 
int ls(int p){return p<<1;}     //返回左儿子标号
int rs(int p){return p<<1|1;}   //返回右儿子标号 
struct scanline{    //扫描线结构体
    int y;          //这根扫描线的y轴 
    int lx,rx;      //左右端点
    int inout;      //入边(1)与出边(-1)
    scanline(){};
    scanline(int y,int lx,int rx,int inout):
            y(y),lx(lx),rx(rx),inout(inout){};
                    //自定义初始化 
}line[maxn*4];
struct tree{
    int sum,len;
    //sum:区间被完全覆盖的长度
    //len:区间被截的长度 
}tree[maxn*4];
int length[maxn*4]={0}; //即每段的宽度
int xx[maxn*4];         //即离散化数组x
bool cmp(scanline a,scanline b){
    return a.y<b.y; //按y坐标排序 
} 
void build(int p,int l,int r){      //建树函数 
     //也没有什么好建的，约等于初始化
     tree[p].sum=tree[p].len=0;
     if(l==r)return;
     int mid=(l+r)>>1;
     build(ls(p),l,mid);
     build(rs(p),mid+1,r); 
}
void pushup(int p,int l,int r){ //更新函数 
    if(tree[p].sum){        //这个区间被覆盖 
        tree[p].len=xx[r+1]-xx[l]; 
        //更新长度 
    }
    else{                   //没有被覆盖 
        tree[p].len=tree[ls(p)].len+tree[rs(p)].len;
        //以它的两个子节点的长度更新该节点 
    } 
} 
void change(int p,int l,int r,int tl,int tr,int io){
    //l,r表示当前所在区间
    //tl,tr表示真实修改区间 
    if(xx[r+1]<=tl||xx[l]>=tr)return;   //out of the range
    if(tl<=xx[l]&&xx[r+1]<=tr){
        tree[p].sum+=io;
        pushup(p,l,r);
        return;
    }
    int mid=(l+r)>>1;
    change(ls(p),l,mid,tl,tr,io);
    change(rs(p),mid+1,r,tl,tr,io);
    pushup(p,l,r);
} 
signed main(){
    cin>>n;
    while(n--){
        cin>>x1>>yy1>>x2>>y2;
        line[++sum]=scanline(yy1,x1,x2,1);
        xx[sum]=x1;
        line[++sum]=scanline(y2,x1,x2,-1);
        xx[sum]=x2;
        //给入边、出边赋值 
    }
    sort(xx+1,xx+sum+1);                //不要忘记排序 
    sort(line+1,line+sum+1,cmp);        //不要忘记排序 
    int num=unique(xx+1,xx+sum+1)-(xx+1);
    //离散化基操
    int l,r; 
    build(1,1,num-1);
    for(int i=1;i<sum;i++){         //对所有入边和出边进行扫描 
        change(1,1,num-1,line[i].lx,line[i].rx,line[i].inout);
        ans+=tree[1].len*(line[i+1].y-line[i].y);
    }
    cout<<ans;
    return 0;
}

从中我们可以看出，scanline 表示的是每根扫描线，而 tree 维护的是各区间 P_i 的和。其他的应该都懂了。

于是我们得到了扫描线题目的一般做法：

建立扫描线结构体，并将每条扫描线初始化（入边、出边）；
将x坐标离散化；
将离散化后的x坐标递增排序，将扫描线按y坐标递增排序；
建立维护各段宽的线段树，并写出建树、插入、合并函数。
遍历每条扫描线，求出最后结果。

The end——？

P1502 窗口的星星

这一题，我们将每个星星看作一个窗口，这个星星为左下角。因为窗口不包括边缘，所以边长都要减 1。

然后就是求矩形的最大 l 值之和，这个就直接用线段树标准解法去求即可。

Code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
int n,x,y,l, t,w,h; 
int ls(int p){return p<<1;} 
int rs(int p){return p<<1|1;}
struct scanline{
    int y;      
    int lx,rx;  
    int inout;  
    scanline(){};
    scanline(int y,int lx,int rx,int inout):
            y(y),lx(lx),rx(rx),inout(inout){};
}line[maxn*4];
struct tree{
    int add,mx;
}tree[maxn*4];
int xx[maxn*4]; 
bool cmp(scanline a,scanline b){
    if(a.y==b.y)return a.inout>b.inout;
    return a.y<b.y;
} 
void init(){
    memset(line,0,sizeof(line));
    memset(tree,0,sizeof(tree));
} 
void build(int p,int l,int r){  
     tree[p].add=tree[p].mx=0;
     if(l==r)return;
     int mid=(l+r)>>1;
     build(ls(p),l,mid);
     build(rs(p),mid+1,r); 
}
void pushdown(int p){
    tree[ls(p)].mx+=tree[p].add;
    tree[rs(p)].mx+=tree[p].add;
    tree[ls(p)].add+=tree[p].add;
    tree[rs(p)].add+=tree[p].add;
    tree[p].add=0;
}
void pushup(int p){ 
    tree[p].mx=max(tree[ls(p)].mx,tree[rs(p)].mx);
} 
void change(int p,int l,int r,int tl,int tr,int io){
    if(l>tr||r<tl)return;
    if(tl<=l&&r<=tr){            
        tree[p].add+=io;
        tree[p].mx+=io;
        return;
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(tl<=mid)change(ls(p),l,mid,tl,tr,io);
    if(mid<r)change(rs(p),mid+1,r,tl,tr,io);
    pushup(p);
} 
signed main(){
    cin>>t;
    while(t--){
        init();
        cin>>n>>w>>h;
        int sum=0,ans=0;
        while(n--){
            cin>>x>>y>>l;
            line[++sum]=scanline(y,x,x+w-1,l);
            xx[sum]=x;
            line[++sum]=scanline(y+h-1,x,x+w-1,-l);
            xx[sum]=x+w-1;
        }
        sort(xx+1,xx+sum+1);        
        sort(line+1,line+sum+1,cmp);
        int num=unique(xx+1,xx+sum+1)-(xx+1);
        int l,r; 
        build(1,1,num);
        for(int i=1;i<=sum;i++){
            change(1,1,num,lower_bound(xx+1,xx+num+1,line[i].lx)-xx,lower_bound(xx+1,xx+num+1,line[i].rx)-xx,line[i].inout);
            ans=max(ans,tree[1].mx);
        }
        cout<<ans<<'\n';
    }
    return 0;
}

未完待续……