扫描线学习笔记

Part 0 前言

其实很久以前就自己看过扫描线，但是由于水平不够+没搞懂的不去搞所以也就今天才真正弄明白了。

Part 1 算法用途

解决在坐标轴上一些与图形有关的问题，包括一堆矩形并的面积、周长等等。

Part 2 算法思想

顾名思义，就是用一条线在坐标轴上扫来扫去。

以求矩形并的面积为例：

现在有 $n$ 个矩形，矩形的四个点的 $x$ 和 $y$ 坐标都 $\in [0,10^9]$ 且为整点，问这些矩形并起来的面积（$n\leq 10^5$）。

---

有一个思路就是对于每个矩形暴力打标记，然后看被标记的点数，时间复杂度：$O(V^2)$。

这样做显然是会爆炸的而且坐标还必须是整数。

考虑优化。

---

注意到值域是远大于 $n$ 的，所以可以把矩形四个点的 $x$ 和 $y$ 离散化下来，这样整个坐标轴就被这些离散化下来的横线和竖线给分割成很多个网格，每个网格里的点是否被标记的状态显然是相同的，所以可以像上面那样暴力打标记，时间复杂度：$O(n^2)$。

像这样：

就直接求每个标蓝网格的面积即可

---

其实算法可以做得更优，设一个矩形为 $(x_1,y_1)-(x_2,y_2)$，类似于差分，可以把它拆成入边和出边。

入边表示在 $x_1$ 把 $[y_1,y_2]$ 的覆盖层数 $+1$，出边表示在 $x_2$ 把 $[y_1,y_2]$ 覆盖层数 $-1$，然后依次扫描离散化出来的线，最后被需要计入总答案的就是当前覆盖层数 $\geq 1$ 的线段总长度 $\times$ 当前两条相邻的线截出的长度，直接数据结构维护可以做到 $O(n\log n)$（详细维护方法见例题）。

---

上面就是扫描线的流程，也就是把直线离散化然后对于被两条相邻的线截开的区域用数据结构维护。

Part 3 例题

P5490 【模板】扫描线

就是上面的模板，然后用线段树维护。

由于要维护当前覆盖层数 $\geq 1$ 的点的个数，考虑记录区间 $\min$ 值、区间 $\min$ 值出现的线段的长度和区间不为 $0$ 的所有线段的长度。

这个显然是可以维护的，前两个直接搞。后面的那个如果区间 $\min$ 值为 $0$，答案就是区间总长度 $-$ 区间 $\min$ 值的线段长度。

如果区间 $\min$ 值不为 $0$，答案就是区间总长度。

时间复杂度：$O(n\log n)$。

Code

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <tuple>
#include <vector>

#define int long long

const int kMaxN = 2e5 + 5;

int n, m, k;
int x1[kMaxN], y1[kMaxN], x2[kMaxN], y2[kMaxN], b[kMaxN], lsh[kMaxN];
int sum[kMaxN << 2], mini[kMaxN << 2], cnt[kMaxN << 2], tag[kMaxN << 2];
std::vector<std::tuple<int, int, int>> v[kMaxN];

void discrete() {
  std::sort(b + 1, b + 1 + m), std::sort(lsh + 1, lsh + 1 + k);
  m = std::unique(b + 1, b + 1 + m) - (b + 1);
  k = std::unique(lsh + 1, lsh + 1 + k) - (lsh + 1);
  for (int i = 1; i <= n; ++i) {
    y1[i] = std::lower_bound(lsh + 1, lsh + 1 + k, y1[i]) - lsh;
    y2[i] = std::lower_bound(lsh + 1, lsh + 1 + k, y2[i]) - lsh;
    v[std::lower_bound(b + 1, b + 1 + m, x1[i]) - b].emplace_back(y1[i], y2[i], 1);
    v[std::lower_bound(b + 1, b + 1 + m, x2[i]) - b].emplace_back(y1[i], y2[i], -1);
  }
}

void pushup(int x) {
  sum[x] = sum[x << 1] + sum[x << 1 | 1];
  if (mini[x << 1] < mini[x << 1 | 1]) {
    mini[x] = mini[x << 1], cnt[x] = cnt[x << 1];
  } else if (mini[x << 1] > mini[x << 1 | 1]) {
    mini[x] = mini[x << 1 | 1], cnt[x] = cnt[x << 1 | 1];
  } else {
    mini[x] = mini[x << 1], cnt[x] = cnt[x << 1] + cnt[x << 1 | 1];
  }
}

void addtag(int x, int l, int r, int v) {
  tag[x] += v, mini[x] += v;
  if (mini[x]) sum[x] = lsh[r + 1] - lsh[l];
  else sum[x] = lsh[r + 1] - lsh[l] - cnt[x];
}

void pushdown(int x, int l, int r) {
  if (!tag[x]) return;
  int mid = (l + r) >> 1;
  addtag(x << 1, l, mid, tag[x]), addtag(x << 1 | 1, mid + 1, r, tag[x]);
  tag[x] = 0;
}

void build(int x, int l, int r) {
  if (l == r) {
    cnt[x] = lsh[r + 1] - lsh[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  pushup(x);
}

void update(int x, int l, int r, int ql, int qr, int v) {
  if (l > qr || r < ql) {
    return;
  } else if (l >= ql && r <= qr) {
    return addtag(x, l, r, v);
  }
  pushdown(x, l, r);
  int mid = (l + r) >> 1;
  update(x << 1, l, mid, ql, qr, v), update(x << 1 | 1, mid + 1, r, ql, qr, v);
  pushup(x);
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) {
    std::cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
    b[++m] = x1[i]; b[++m] = x2[i];
    lsh[++k] = y1[i]; lsh[++k] = y2[i];
  }
  discrete();
  long long ans = 0;
  build(1, 1, k - 1);
  for (int i = 1; i < m; ++i) {
    for (auto p : v[i]) {
      int l = std::get<0>(p), r = std::get<1>(p), c = std::get<2>(p);
      update(1, 1, k - 1, l, r - 1, c);
    }
    ans += 1ll * (b[i + 1] - b[i]) * sum[1];
  }
  std::cout << ans << '\n';
}

int32_t main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << 's' << endl;
  return 0;
}

未完待续…