[算法] 扫描线

[0.x]前言

扫描线算法(ScanLine)用于求矩阵面积并或周长并，内核为线段树维护离散化的线段并在线处理。

语言：

为了节省时间，图片全部引自这篇Luogu题解

目录

• [1.x]扫描线概述
• [2.x]扫描线实现
  • [2.1.x]预处理&离散化
  • [2.2.x]线段树维护
  • [2.3.x]在线处理
• [3.x]相关代码

[1.x]扫描线概述

扫描线一般用于处理以下问题：

读入若干矩阵，求矩阵的周长并/面积并。

该问题的处理难点在于：

• 当用点来维护矩阵的时候，数值可能过大，需要离散化
• 维护完点集以后，暴力计算处理繁复而且缓慢，需要线段树维护

我们用线段树维护从下到上的每一个线段，每一次向上推移一个离散后的单位长度，进行求解，就可以得到每一部分的面积

• 如我们维护x[1]~x[3]的长度，乘以两条红色线之间的距离，就是这个绿色区域的面积

[2.x]扫描线实现

[2.1.x]预处理&离散化

我们需要预处理的东西主要有以下几个：

• 维护每一条横向线段，包括左端点和右端点，以及线段的高度和属性（即这条边是一个矩形的上边还是下边）

line[++tot].l = x_1 , line[tot].r = x_2 , line[tot].h = y_1 , line[tot].v = 1;
line[++tot].l = x_1 , line[tot].r = x_2 , line[tot].h = y_2 , line[tot].v = -1;
//我们定义下边的权值为+1，因为我们扫到一个下边就意味着有一个新的区域要加入计算
//我们定义上边的权值为-1，因为我们扫到一个上边就意味着有一个旧的区域要脱离计算
std::sort(line+1,line+tot_line+1,cmp);
//按照高度(line[tot].h)排序，因为我们处理的时候是从下往上处理的

• 维护所有端点的横座标并去重以便离散化

//两个代码框之间的tot不共通，只是为了缩小代码块码量，请主要区分
point[++tot] = x_1 , point[++tot] = x_2;
//存入所有的横座标
std::sort(point+1,point+tot_point+1,cmp);
tot_x = std::unique(point+1,point+tot+1)-point-1;
//排序后去重，用来离散化

[2.2.x]线段树维护

我们用线段树维护线段而非点。

对于一个节点cur，我们有这么几个属性：

• cur->l，表示离散化后的该线段左端点序号
• cur->r，表示离散化后的该线段右端点序号的前一个，即真正的右端点应该为point[cur->r+1]
• cur->len，表示当前节点所表示的线段里已经被标记过的有多长
• cur->sum，表示该线段被标记与否
  • 其实这里可以用bool类型，但是我们刚才定义了上下边为1/-1，所以可以用int的加减来实现0/1即T/F的转换
• cur->ls``cur->rs，左儿子右儿子，不解释

struct node{
    int l,r;
    ll sum,len;
    node * ls, * rs;
}Tree[4*N];

其中特别要注意的就是，我们维护的是线段，而cur->r这个属性维护的前一个序号，这就能保证线段树的线段没有重复但是维护的线段端点可以重合。

另外，之所以这里不用打tag，是因为这里有个特殊的性质：

• 对于一个节点，也就是对于一条特定的线段，它一定存在偶数个待处理线段，这是由输入的东西是矩阵保证的。换句话说，你要是这个节点被标记了，那说明这上面的一定都可以，不存在因为子节点的修改而导致该节点的变化。所以既不需要pushdown也不需要lazy_tag。
• 再换句话说，对于线段上的任意一点，只要经过改点的线段有一条是被标记的，就可以纳入计算。

inline node * create(){return &Tree[++tot_tree];} // 线段树申请节点
inline void build(node * cur,int l,int r){ // 线段树建树
    cur->l = l , cur->r = r , cur->sum = cur->len = 0; // 节点初始化
    if(l == r) return;
    int mid = (l+r)>>1;
    cur->ls = create() , cur->rs = create();
    build(cur->ls,l,mid) , build(cur->rs,mid+1,r);
    return;
}
inline void pushup(node * cur){ // 喜闻乐见的pushup
    if(cur->sum) cur->len = point[cur->r+1] - point[cur->l]; // 如果当前节点被标记就直接用当前线段长度
    else cur->len = cur->ls->len + cur->rs->len; // 当前节点没被标记就用儿子的
}
inline void edit(node * cur,int k){
    int l = cur->l , r = cur->r;
    if(L >= point[r+1] || R <= point[l]) return;
    if(L <= point[l] && R >= point[r+1]){
        cur->sum += k;
        if(cur->l != cur->r) pushup(cur);
        else{ if(cur->sum) cur->len = point[cur->r+1] - point[cur->l];else cur->len = 0;}
        return;
    }
    edit(cur->ls,k) , edit(cur->rs,k);
    pushup(cur);
    return;
}
int main(){
    ...
    node * root = create();
    build(root,1,tot_x-1); // n个点，n-1个独立线段
    ...
}

[2.3.x]在线处理

我们现在已经用线段树维护这些线段了，也维护了从下到上的线段，我们只需要从下到上一个个枚举这些线段就行了。

rep(i,1,tot_line){
    L = line[i].l , R = line[i].r; // 全局变量减少函数传参
    edit(root,line[i].v);pushup(root); // 在线维护扫描线上的标记长度
    ans += root->len * (line[i+1].h - line[i].h); // 计算
}

[3.x]相关代码

P5490 【模板】扫描线

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for(register int i = (a);i <= (b);++i)
#define per(i,a,b) for(register int i = (a);i >= (b);--i)  
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;
const int N = 100010;
int n,x_1,x_2,y_1,y_2,tot_line,tot_x,tot_point,tot_tree,L,R;
ll point[4*N],ans;
struct LINE{
    int l,r,h,v;
}line[4*N];
struct node{
    int l,r;
    ll sum,len;
    node * ls, * rs;
}Tree[4*N];
inline bool cmp1(LINE a,LINE b){return a.h<b.h;}
inline bool cmp2(int x,int y){return x<y;}
inline node * create(){return &Tree[++tot_tree];}
inline void build(node * cur,int l,int r){
    cur->l = l , cur->r = r , cur->sum = cur->len = 0;
    if(l == r) return;
    int mid = (l+r)>>1;
    cur->ls = create() , cur->rs = create();
    build(cur->ls,l,mid) , build(cur->rs,mid+1,r);
    return;
}
inline void pushup(node * cur){
    if(cur->sum) cur->len = point[cur->r+1] - point[cur->l];
    else cur->len = cur->ls->len + cur->rs->len;
}
inline void edit(node * cur,int k){
    int l = cur->l , r = cur->r;
    if(L >= point[r+1] || R <= point[l]) return;
    if(L <= point[l] && R >= point[r+1]){
        cur->sum += k;
        if(cur->l != cur->r) pushup(cur);
        else{ if(cur->sum) cur->len = point[cur->r+1] - point[cur->l];else cur->len = 0;}
        return;
    }
    edit(cur->ls,k) , edit(cur->rs,k);
    pushup(cur);
    return;
}
int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("in.in", "r", stdin);
    cin >> n;
    rep(i,1,n){
        cin >> x_1 >> y_1 >> x_2 >> y_2;
        line[++tot_line].l = x_1 , line[tot_line].r = x_2 , line[tot_line].h = y_1 , line[tot_line].v = 1;
        line[++tot_line].l = x_1 , line[tot_line].r = x_2 , line[tot_line].h = y_2 , line[tot_line].v = -1;
        point[++tot_point] = x_1 , point[++tot_point] = x_2; 
    }
    std::sort(line+1,line+tot_line+1,cmp1) , std::sort(point+1,point+tot_point+1,cmp2);
    tot_x = std::unique(point+1,point+tot_point+1)-point-1;
    node * root = create();
    build(root,1,tot_x-1);
    rep(i,1,tot_line){
        L = line[i].l , R = line[i].r;
        edit(root,line[i].v);pushup(root);
        ans += root->len * (line[i+1].h - line[i].h);
    }
    cout << ans << "\n";
    return 0;
}