【恐怖の算法】 扫描线

引入

扫描线一般运用在图形上面，它和它的字面意思十分相似，就是一条线在整个图上扫来扫去，它一般被用来解决图形面积，周长，以及二维数点等问题。

二维矩形面积并问题

在二维坐标系上，给出多个矩形的左下以及右上坐标，求出所有矩形构成的图形的面积。

过程

根据图片可知总面积可以直接暴力即可求出面积，如果数据大了怎么办？这时就需要讲到 扫描线 算法。

现在假设我们有一根线，从下往上开始扫描：

按这样把矩形分成几个部分，小矩形的高是扫过的距离。我们可以发现，小矩形的宽一直在变化。

给每一个矩形的上下边进行标记，下面的边标记为 1，上面的边标记为 -1。每遇到一个水平边时，让这条边（在横轴投影区间）的权值加上这条边的标记。

小矩形（不一定只有一个）的宽度就是整个数轴上权值大于 0 的区间总长度。

实现

很容易想到可以用线段树。

用线段树维护矩形的长，也就是整个数轴上覆盖次数大于 0 的点。

需求列举如下：

• 一段区间权值加 1、减 1。

• 统计整个数轴上，区间权值大于 0 的「区间长度和」。

如果你尝试直接用普通线段树模板来实现的话，也许会遇到些挫折。具体地，由于在区间加时，即使修改区间和节点管理区间重合，我们还是不能常数时间知道覆盖次数如何变化。这是因为我们不能直接知道：管理范围里有多长的区间会从 1 变成 0（从 0 变成 1）。

这道题只需要朴素的分治就能实现：维护每个节点管理区间中「整体 修改的权值和 w[]」（类似不用下放的懒惰标记）和「覆盖长度 v[]」两个信息。

需要用到离散化。

例题

题目传送门：CZOJ #25.「模板」扫描线

分析

模版题，同理直接用线段树

离散化+线段树+模拟

由于数据量太大，我们先把所有的墙壁离散化，用线段树维护每个离散化后的横坐标的最高点，然后模拟求出答案。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int n;
struct a {
    int x;
    int h;
    int v;
    int l;
} r[200005] = {};
int d[100005] = {};
int cmh(a x, a y) { return x.h < y.h; }
int cmx(a x, a y) { return x.x < y.x; }
int t[400005] = {};
int m = 0, ans[400005][2] = {};
void ad(int k, int x, int l, int r, int v) {
    int mid = (l + r) / 2;
    t[k] += v;
    if (l != r) {
        if (x <= mid) {
            ad(k * 2, x, l, mid, v);
        } else {
            ad(k * 2 + 1, x, mid + 1, r, v);
        }
    }
}
int rank(int k, int l, int r) {
    int mid = (l + r) / 2;
    if (t[k] == 0) {
        return 0;
    }
    if (l == r) {
        return mid;
    }
    if (t[k * 2 + 1] == 0) {
        rank(k * 2, l, mid);
    } else {
        rank(k * 2 + 1, mid + 1, r);
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> r[i * 2].h >> r[i * 2 - 1].x >> r[i * 2].x;
        r[i * 2 - 1].h = r[i * 2].h;
        r[i * 2 - 1].v = 1;
        r[i * 2].v = -1;
    }
    sort(r + 1, r + 2 * n + 1, cmh);
    r[0].x = 1000000001;
    r[2 * n + 1].x = r[0].x;
    for (int i = 1; i <= 2 * n; i++) {
        r[i].l = r[i - 1].l + (r[i].h != r[i - 1].h);
        d[r[i].l] = r[i].h;
    }
    sort(r + 1, r + 2 * n + 1, cmx);
    int i = 1, j = 1;
    int now = 0, pas = 0;
    while (i <= 2 * n) {
        j = i;
        while (r[j].x == r[i].x) {
            ad(1, r[i].l, 1, 100000, r[i].v);
            now = rank(1, 1, 100000);
            i++;
        }
        if (pas != now) {
            m++;
            ans[m][0] = r[j].x;
            ans[m][1] = d[pas];
            m++;
            ans[m][0] = r[j].x;
            ans[m][1] = d[now];
            pas = now;
        }
    }
    ans[m][1] = 0;
    cout << m << endl;
    for (int i = 1; i <= m; i++) {
        cout << ans[i][0] << " " << ans[i][1] << endl;
    }
}

噩梦算法の终结~