题解 P5490 【【模板】扫描线】

dzz1537568241 · 2019-09-26 21:28:37 · 题解

这是一篇扫描线的题解....

本文包括：

离散化在线段树上的应用
手把手的建立扫描线
代码的具体分析

在开始之前，你必须熟练掌握

离散化
线段树

检测离散化孰不熟练的方式有P1955

离散化真的很重要，当时作为一个什么离散化都不懂的萌新读扫描线的代码真的什么都看不懂

1. 离散化

在进行扫描线之前必须要普及离散化的概念和意义

首先什么是离散化？我们为什么要离散化？

离散化是把一系列数字，按照从小到大的顺序排列后，能够快速找到这个数组第k大的数字，这就是所谓离散化

（如果你发现与定义不同，没关系，我只是直接从代码出发而已）

分析一下：你要找到一个数组中第k大的数字，该怎么办？

我们的思路是直接通过下标访问：

举个栗子，如果要访问第k大的数，最简单粗暴的访问方式就是a[k]，那么为了实现这个目标，我们有以下操作：

目标：直接访问下标来达到访问第k大的数，那么需要先把a数组排一遍序
排序后，数组内不能含有重复元素，因此需要去除重复元素。

就两步操作就能完成离散化。

写出伪代码：

//对 a 数组的元素进行离散化操作，以保证能快速访问到 a 数组中第 k 大的数 
int a[maxn];
将 a 数组 进行排序
去除 a 数组 的重复的元素

STL的去重函数是 unique ( 数组头指针，数组尾指针）

返回值是被去重之后的数组的尾指针

特别需要注意的是unique只对排过序的数组生效

代码：

//对 a 数组的元素进行离散化操作，以保证能快速访问到 a 数组中第 k 大的数 
#include <algorithm>
int a[maxn], tail;//tail是 a 数组的尾指针 
sort(a + 1, a + 1 + tail);
tail = unique(a + 1, a + 1 + tail) - (a + 1);//对a数组去重，并且更新a数组的尾指针

离散化后的数组的访问操作：

访问一个元素在a数组的位置：
```
lower_bound(a + 1, a + 1 + tail) - a; 
```
访问a数组第k个元素的值：

    a[k]

2. 用一维的数据结构维护二维信息

扫描线真的不难，只要用点心，是绝对学的会的

嗯如果你需要看演示，这里有一个很好的扫描线演示

感谢@Gu_Pigeon 的题解

在这里我给你做的是分析代码和代码实现，演示就看上面的链接就吼了

分析题目：这是一个求出矩形的并集的面积的问题，可以理解为某一个区间并集，区间操作很容易想到什么？对，线段树
线段树三连：

线段树维护什么
怎么修改区间的值
怎么维护父节点

事实上，一个线段树能够维护的是一个区间，你可以想象成一根数轴。问题来了：怎么在一个只能够维护 一根线段上的点的信息 的数据结构上处理一个二维平面上的信息？

吼吼，这个时候就需要请出扫描线大神了

虽然线段树只能维护一维的信息，但是线段树支持 加点删点 的操作啊！

那我们每次把一维的信息加进去之后进行维护不就好了嘛

什么意思呢？

（感谢@Gu_Pigeon提供的图片，侵权立删）

线段树维护的是 y 轴上的长度，然后每一次“加入一维的信息”的意思是在每一次加入进去的是 垂直于某一个x轴上的点的信息，画图示意一下 ~~（有点丑）~~

想象一根线段垂直于x轴，向x轴正半轴一点一点往右移动，

当遇到一条垂直x轴的矩形的边的时候，就将这个矩形边上的所有信息加入线段树

写出伪代码：

for (遍历x轴上所有的点){
    if(垂直于这个x轴上的线段上 有矩形的 点){
        将处于这条线段上的所有点的信息全部加入线段树 
    } 
}

这样就可以让线段树 维护二维信息 了

3. 线段树

看题，要求 求出所有的矩形的并集的覆盖的面积

对比一下刚刚扫描线完成的操作：

for (遍历x轴上所有的点){
    if(垂直于这个x轴上的线段上 有矩形的 点){
        将处于这条线段上的所有点的信息全部加入线段树 
    } 
}

思考一下线段树里维护的是什么：
想像一下.....一条线段往右扫，一旦发现了矩形竖直的一条边，那么就把这条边的信息加入线段树，再用一次这张图

举个例子，如下图

如果扫到x = k1的时候，x = k1 处的线段的信息被加入线段树，当扫到 x = k2 处的时候，发现 要维护 [ k1, k2 ] 处区间的面积，那怎么办呢？

很简单，S = （ x = k1 处的线段长度） * （ k1 - k2 ）

那线段树上该维护点啥？

当然是维护 x = k1处的线段长度喽

改进一下之前的伪代码：

for (遍历x轴上所有的点){ 
    if(该条直线 k1 上 存在矩形 一条边 ){
        //线段树上用来维护边的长度 
        更新线段树上的边的长度 
        面积 =  （ k1 - 上一个矩形的边 横坐标） * 线段树上的边的长度 
    } 
}

4.读入扫描线

我们需要 存储每一段的扫描线，看图，每一段扫描线只需要三个参量：

x 轴坐标
矩形 y 坐标的上界
矩形 y 坐标的下界

而当我们遍历的时候，只需要将 x 轴坐标进行从左到右的一遍排序即可，写出伪代码：

struct Scanline{
    int x, y1, y2;
}scanline[ maxn ];

int main(){
    for(输入操作){
        读入矩形的四个坐标x1, y1, x2, y2
        scanline 加入(x1, y1, y2);
        scanline 加入(x2, y1, y2); 
    }

    将扫描线按照x轴的坐标从小到大排序 

    for (遍历所有的扫描线){ 
        //线段树上用来维护边的长度 
        更新线段树上的边的长度 
        面积 =  （ k1 - 上一个矩形的边 横坐标） * 线段树上的边的长度 

    }
}

现在只剩下怎么维护线段树了，~~胜利在望~~

已经可以确定线段树必须要维护的值有：

线段 y 坐标的上界和下界
该区间内线段的总长度

即

struct segment_tree{
    int l, r, len;
    //l:y坐标的上界
    //r:y坐标的下界
        //len:当前区间内线段的总长度
}st[ maxn ];

同时，这个线段树应该支持

删除操作（加入线段之后再更新完这块面积之后得删去之前加进来的线段）
支持求出当前线段总长度

求出线段总长度

其实就是怎么用子区间去更新父节点，没什么难度，写出伪代码：

struct segment_tree{
    int l, r, len;
    //l:y坐标的上界
    //r:y坐标的下界
        //len:当前区间内线段的总长度
}st[ maxn ];

void pushup(int o){
    st[o].len = st[o << 1].len + st[o << 1| 1].len;
    //父节点的区间值 = 子区间的长度之和 
}

删除操作

现在来考虑删除操作，什么时候需要删除一条边？

当扫描到矩形的右侧边的时候，就得删除之前加进来的边

思考：线段树支持些什么？

区间修改值
区间合并

对，线段树是支持区间修改值的，那怎么修改这个区间的值，以及怎么判断此时需要修改呢？

当前边是矩形左侧边的时候加入线段树
当前边是矩形右侧边的时候从线段树中删除

我们需要为扫描线引进 新变量mark，用来判断这是左边还是右边，左半边的线段记为1，右半边的线段记为 -1

struct Scanline{
    int x, y1, y2，mark;
}scanline[ maxn ];

int main(){
    for(输入操作){
        读入矩形的四个坐标x1, y1, x2, y2

        //这是矩形的左半边
        scanline 加入(x1, y1, y2, 1);

        //这是矩形的右半边
        scanline 加入(x2, y1, y2, -1); 
    }
}

同时我们应该为线段树添加新变量来判断是否被一个矩形的边完全覆盖

如果当前区间被一个矩形的边完全覆盖的时候, 区间的长度 = 上界 - 下界( r - l )
如果没有被矩形边完全覆盖，用左区间和右区间的长度 来更新它自己的长度

伪代码：

struct segment_tree{
    int l, r, len;
    //l:y坐标的上界
    //r:y坐标的下界
     //len:当前区间内线段的总长度

    int mark;
        //mark:判断区间内是否被矩形的边完全覆盖
}st[ maxn ];

void pushup(int o){
    if(mark //o 这个区间被矩形的边完全覆盖)st[o].len = st[o].r - st[o].l;
    else{
        st[o].len = st[o << 1].len + st[o << 1| 1].len;
        //父节点的区间值 = 子区间的长度之和 
    }   
}

区间修改操作：

如果这条扫描线是矩形的左半边, 给被覆盖的线段的mark + 1
如果这条扫描线是矩形的右半边，给被覆盖的线段的mark - 1

这样就能通过mark来完成区间的删除和加入，写出加入&删除边的

伪代码：

void change(int o, int L, int R,int mark){
    //o:当前区间
    //L:要改变的区间上界
    //R:要改变的区间下界
    int l = st[o].l, r = st[o].r;//当前区间的左右端点
    if(L <= l && r <= R){
        st[o].mark += mark;
        pushup(o);
        return; 
    } 
    int mid = (l + r) >> 1;
    if(L <= mid)change(o << 1, L, mid);
    if(mid + 1 <= R)change(o << 1, mid + 1, R, mark);
    pushup(o);
}

至于建树太简单了就不讲了，就是初始化一下，没什么特别的

到这里就可以把所有的伪代码给出来了

struct segment_tree{
    int l, r, len;
    //l:y坐标的上界
    //r:y坐标的下界
    //len:当前区间内线段的总长度

    int mark;
    //mark:判断区间内是否被矩形的边完全覆盖，用于完成区间的删除操作 
}st[ maxn ];

void build(int o, int l, int r){
    st[o].l = l, st[o].r = r;
    st[o].len = 0;
    st[o].mark = 0;
    if(l == r)return;
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1|1, mid + 1, r);
}
void pushup(int o){
    if(st[o].mark)st[o].len = st[o].r - st[o].l;
    else{
        st[o].len = st[o << 1].len + st[o << 1| 1].len;
        //父节点的区间值 = 子区间的长度之和 
    }   
}

void change(int o, int L, int R,int mark){
    //o:当前区间
    //L:要改变的区间上界
    //R:要改变的区间下界
    int l = st[o].l, r = st[o].r;//当前区间的左右端点
    if(L <= l && r <= R){
        st[o].mark += mark;
        pushup(o);
        return; 
    } 
    int mid = (l + r) >> 1;
    if(L <= mid)change(o << 1, L, mid);
    if(mid + 1 <= R)change(o << 1, mid + 1, R, mark);
    pushup(o);
}

struct Scanline{
    int x, y1, y2，mark;
}scanline[ maxn ];

int main(){
    for(输入操作){
        读入矩形的四个坐标x1, y1, x2, y2
        scanline 加入(x1, y1, y2, 1);
        scanline 加入(x2, y1, y2, -1); 
    }

    将扫描线按照x轴的坐标从小到大排序 

    for (int i = 1; i <= N; i++){//扫描线的个数 
        //线段树上用来维护边的长度 
        change(1, scanline[i].l, scanline[i].r, scanline[i].mark);
        面积 =  （ k1 - 上一个矩形的边 横坐标） * st[1].len;
    }
}

把思路理一遍：

线段树用于处理一维的线段长度
判断是矩形的左边还是右边，是左边就加，是右边则减

就这么两个难点

离散化

你们以为就这么结束了嘛哈哈哈哈哈哈，当然不可能，

不然我前面白讲了那么久离散化了，

现在我们要为线段树加上离散化这一个优化

在开始之前建议温故而知新
记住线段树履行的功能：求线段总和

so，what need 离散化？

还记得离散化的功能？将一个数轴上的一个一个点通过大小排序，保留点与点的大小关系

这道题目的线段树是绝对不会允许你开四倍于线段长度的，百分百爆掉，这个时候就需要进行离散化，
离散化的原因是： 线段树的长度不能开的太大

那很明显我们要离散化的是：

扫描线上的 y 坐标上界和 y 坐标下界

我们把所有的矩形边上的 y 坐标存储下来

不是矩形边上的y坐标 是不需要使用的，（因为只需要l - r就能够知道边上的长度），因此可以对y进行离散化操作

给出离散化的代码：

//Y:矩形边上的所有Y坐标
#include <algorithm>
int Y[ maxn ];
sort(Y + 1, Y + 1 + N);
tot = unique(Y + 1, Y + 1 + N);

好，接下来是把离散化丢进线段树里去

线段树的意义也发生改变了，现在它维护的 l, r 不再是数值意义上的l, r，而是被离散化后的 l, r的排名。

接下来是最后一个难点了，加油！！！

这里有一个很不错的图文解说，描述了离散化怎么作用在线段树上

@sdau_blue 的一篇博客

被离散化后的线段树的l, r 存储的是区间( Y[ l ], Y[ r ] ），但，当l = r 的时候，即为（Y[l] , Y[l]）,变成了一个点。

变成了一个点有什么问题咧？

问题大着呢

感谢@MakiseVon 提供的例子

举个栗子，如果总区间为[1, 4],

有一条扫描线，y1 = Y[1] , y2 = Y[3] ,加入线段树，模拟一下：

进入到线段树修改值，修改st[1,2]的长度为Y[2] - Y[1]

修改st[3,3]的长度为Y[3] - Y[3] = 0

等等这显然不对啊, st[3,3]的值应该被修改成Y[3] - Y[2]才对

因此我们想到了改变 线段树存储的值 de意义

用 L 表示左区间 L ，值为Y[L]

用 R 表示 右区间 R + 1 ,值为Y[R + 1]

好，现在再来看之前的例子

有一条扫描线，y1 = Y[1] , y2 = Y[3] ,加入线段树，模拟一下：

进入到线段树修改值，修改st[1,2]的长度为Y[2 + 1] - Y[1]

这样就没问题了

给出全部的代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long 
using namespace std;
const int maxn = 1e6 + 10;
int N, cnt = 0;
ll int x1, x2, y1, y2, X[maxn << 1];
struct scanline{
    ll l, r, h;
    int mark;//保存权值
    bool operator <(const scanline &te)const{
        return h  < te.h;
    } 
}line[maxn << 1];

struct tree{
    int l, r, sum;
    //sum:被完全覆盖的次数
    //len:区间被截的长度 
    ll len; 
}st[maxn << 2];

void build(int o, int l, int r){
    st[o].l = l, st[o].r = r;
    st[o].len = 0;
    st[o].sum = 0;
    if(l == r)return;
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1|1, mid + 1, r);
}
void pushup(int o){
    int l = st[o].l, r = st[o].r;
    if(st[o].sum)st[o].len = X[r + 1] - X[l];//已经被覆盖了，更新长度 
    else{st[o].len = st[o << 1].len + st[o << 1 |1].len;}
}
void change(int o, ll L, ll R, int c){
    int l = st[o].l, r = st[o].r;
    //l,r代表o这个点的范围，L,R意义是待修改的区间
    if( X[r + 1] <= L || R <= X[l] )return;
    //当右区间 + 1小于左区间， 
    if(L <= X[l] && X[r + 1] <= R){
        st[o].sum += c;
        pushup(o);
        return;
    }
    change(o << 1, L, R, c);
    change(o << 1 | 1, L, R, c);
    pushup(o);
}
int main(){
    scanf("%d",&N);
    for(int i = 1; i <= N; i++){
        cin>>x1>>y1>>x2>>y2;
        X[2 * i - 1] = x1, X[2 * i] = x2;
        line[2 * i - 1] = (scanline){ x1, x2, y1, 1};
        line[2 * i] = (scanline){ x1, x2, y2, -1};
    }
    N = N << 1;
    sort(line + 1, line + N +1);
    sort(X + 1, X + N + 1);
    int tot = unique(X + 1, X + N + 1) - (X + 1);
    build(1, 1 , tot - 1);
    //右端点的对应关系已经被修改了,我们用 
    //[1,tot - 1]描述的是[x[1],x[tot]] 
    ll ans = 0;
    for(int i = 1; i < N; i++){
        change(1, line[i].l,line[i].r,line[i].mark);
        ans += st[1].len *(line[i + 1].h - line[i].h);
    }
    cout<<ans;
}

我还特意把Y改成了X，目的就是为让各位练习一下从左到右的扫描线，嗯，就顺着刚才的思路打一遍看看打不打得下来，不记得就类比一下这个代码