Bỏ qua

Quét đường (Scanning Line)

Dẫn nhập

Thuật toán quét (scanning line, hay còn gọi là "quét đường thẳng" hoặc "scanline") thường được sử dụng trong các bài toán hình học. Đúng như tên gọi, ý tưởng là dùng một đường thẳng "quét" qua toàn bộ hình, thường để giải các bài toán về diện tích, chu vi, hoặc đếm số điểm trong hình hai chiều.

Bài toán hợp diện tích hình chữ nhật trong mặt phẳng

Trên hệ tọa độ hai chiều, cho nhiều hình chữ nhật với tọa độ góc dưới trái và góc trên phải, hãy tính tổng diện tích hợp của tất cả các hình chữ nhật này.

Quy trình

Quan sát hình vẽ, tổng diện tích có thể tính vét cạn, nhưng nếu dữ liệu lớn thì cần dùng thuật toán quét.

Giả sử ta có một đường thẳng quét từ dưới lên trên:

Như hình, mỗi lần quét, ta chia mặt phẳng thành các dải màu khác nhau, mỗi dải có chiều cao là khoảng cách quét, còn chiều rộng thay đổi liên tục.

Gán nhãn cho mỗi cạnh ngang của hình chữ nhật: cạnh dưới gán \(+1\), cạnh trên gán \(-1\). Mỗi khi gặp một cạnh ngang, ta cộng/trừ giá trị này vào đoạn tương ứng trên trục hoành.

Lưu ý

Thao tác này giống như duyệt một chuỗi ngoặc: mở ngoặc cộng 1, đóng ngoặc trừ 1, "giá trị" tại mỗi vị trí chính là độ sâu hiện tại, kiểm tra giá trị lớn hơn 0 tương đương với việc đang nằm trong một cặp ngoặc, tức là đoạn này thuộc về hình chữ nhật.

Chiều rộng của các dải nhỏ (có thể có nhiều dải) chính là tổng độ dài các đoạn trên trục hoành có giá trị lớn hơn 0.

Cài đặt

Dùng cây đoạn (segment tree) để duy trì tổng độ dài các đoạn trên trục hoành có số lần phủ lớn hơn 0.

Yêu cầu:

  • Cộng/trừ 1 cho một đoạn.
  • Tính tổng độ dài các đoạn có giá trị lớn hơn 0 trên toàn trục.

Nếu bạn thử dùng cây đoạn thông thường, có thể gặp khó khăn: khi cập nhật một đoạn, dù biết đoạn đó trùng với nút quản lý, ta vẫn không thể biết ngay số đoạn chuyển từ 1 về 0 (hoặc ngược lại).

Giải pháp là: với mỗi nút, duy trì số lần phủ hoàn toàn (v[], giống như lazy tag không cần đẩy xuống) và tổng độ dài đã phủ (w[]).

Cần rời rạc hóa.

LuoGu P5490【Mẫu】Quét & Hợp diện tích hình chữ nhật - Mã mẫu 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <algorithm>
#include <iostream>

using ll = long long;
constexpr int N = 1e5 + 1;

int n, a[N * 2], tot;   // a[] 和 tot 用于把 x 离散化
ll v[N * 8], w[N * 8];  // 完全覆盖区间的次数、已覆盖的长度

struct St {
  ll x1, x2, y, o;
} b[N * 2];  // 矩形上下边缘

int f(int y) {  // 离散化，把坐标映射到 a 中的下标
  return std::lower_bound(a, a + tot, y) - a;
}

void up(int u, int ul, int ur) {  // pushup
  if (v[u]) w[u] = a[ur] - a[ul];
  // 如果对叶子节点调用 w[u*2+1]，那么线段树需要开 8 倍空间
  // 乘上矩形上下两边就是 16 倍
  else if (ul + 1 == ur)
    w[u] = 0;
  else
    w[u] = w[u * 2 + 1] + w[u * 2 + 2];
}

void add(int lf, int rg, ll o, int u = 0, int ul = 0, int ur = tot - 1) {
  // 区间加
  if (lf == ul && rg == ur) return v[u] += o, up(u, ul, ur), void();
  int um = (ul + ur) / 2;
  if (lf < um) add(lf, std::min(rg, um), o, u * 2 + 1, ul, um);
  if (um < rg) add(std::max(lf, um), rg, o, u * 2 + 2, um, ur);
  up(u, ul, ur);
}

int main() {
  std::cin >> n;
  for (int i = 0, x1, x2, y1, y2; i < n; i++) {
    // y1 是局部变量不会重名
    std::cin >> x1 >> y1 >> x2 >> y2;
    b[i] = {x1, x2, y1, 1};
    b[i + n] = {x1, x2, y2, -1};
    a[i] = x1, a[i + n] = x2;
  }

  std::sort(a, a + n * 2), tot = 1;
  for (int i = 1; i < n * 2; i++)
    if (a[i] != a[tot - 1]) a[tot++] = a[i];  // 离散化

  std::sort(b, b + n * 2,
            [](St &i, St &j) -> bool { return i.y < j.y; });  // 操作排序

  ll sum = 0;
  add(f(b[0].x1), f(b[0].x2), 1);
  for (int i = 1; i < n * 2; i++) {
    int x1 = f(b[i].x1), x2 = f(b[i].x2);
    sum += (b[i].y - b[i - 1].y) * w[0];  // 对每个小矩形面积求和
    add(x1, x2, b[i].o);
  }
  std::cout << sum << '\n';
}
[POJ 1151 Atlantis] (http://poj.org/problem?id=1151) - Mã mẫu 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <algorithm>
#include <cstdio>
#include <cstring>
constexpr int MAXN = 300;
using namespace std;

int lazy[MAXN << 3];  // 标记了这条线段出现的次数
double s[MAXN << 3];

struct node1 {
  double l, r;
  double sum;
} cl[MAXN << 3];  // 线段树

struct node2 {
  double x, y1, y2;
  int flag;
} p[MAXN << 3];  // 坐标

// 定义sort比较
bool cmp(node2 a, node2 b) { return a.x < b.x; }

// 上传
void pushup(int rt) {
  if (lazy[rt] > 0)
    cl[rt].sum = cl[rt].r - cl[rt].l;
  else
    cl[rt].sum = cl[rt * 2].sum + cl[rt * 2 + 1].sum;
}

// 建树
void build(int rt, int l, int r) {
  if (r - l > 1) {
    cl[rt].l = s[l];
    cl[rt].r = s[r];
    build(rt * 2, l, (l + r) / 2);
    build(rt * 2 + 1, (l + r) / 2, r);
    pushup(rt);
  } else {
    cl[rt].l = s[l];
    cl[rt].r = s[r];
    cl[rt].sum = 0;
  }
  return;
}

// 更新
void update(int rt, double y1, double y2, int flag) {
  if (cl[rt].l == y1 && cl[rt].r == y2) {
    lazy[rt] += flag;
    pushup(rt);
    return;
  } else {
    if (cl[rt * 2].r > y1) update(rt * 2, y1, min(cl[rt * 2].r, y2), flag);
    if (cl[rt * 2 + 1].l < y2)
      update(rt * 2 + 1, max(cl[rt * 2 + 1].l, y1), y2, flag);
    pushup(rt);
  }
}

int main() {
  int temp = 1, n;
  double x1, y1, x2, y2, ans;
  while (scanf("%d", &n) && n) {
    ans = 0;
    for (int i = 0; i < n; i++) {
      scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
      p[i].x = x1;
      p[i].y1 = y1;
      p[i].y2 = y2;
      p[i].flag = 1;
      p[i + n].x = x2;
      p[i + n].y1 = y1;
      p[i + n].y2 = y2;
      p[i + n].flag = -1;
      s[i + 1] = y1;
      s[i + n + 1] = y2;
    }
    sort(s + 1, s + (2 * n + 1));  // 离散化
    sort(p, p + 2 * n, cmp);  // 把矩形的边的横坐标从小到大排序
    build(1, 1, 2 * n);       // 建树
    memset(lazy, 0, sizeof(lazy));
    update(1, p[0].y1, p[0].y2, p[0].flag);
    for (int i = 1; i < 2 * n; i++) {
      ans += (p[i].x - p[i - 1].x) * cl[1].sum;
      update(1, p[i].y1, p[i].y2, p[i].flag);
    }
    printf("Test case #%d\nTotal explored area: %.2lf\n\n", temp++, ans);
  }
  return 0;
}

Bài tập luyện tập

Hình hộp trực giao B chiều

Hình hộp trực giao B chiều là tập các điểm trong không gian \(B\) chiều, với mỗi chiều \(i\) có tọa độ nằm trong đoạn \([l_i, r_i]\).

Thông thường, đoạn 1 chiều gọi là "đoạn", 2 chiều gọi là "hình chữ nhật", 3 chiều gọi là "hình hộp" (bài toán đếm điểm trong hình chữ nhật 2D là bài toán hình hộp trực giao 2 chiều).

Với bài toán tĩnh hai chiều, ta có thể dùng quét một chiều, cấu trúc dữ liệu duy trì chiều còn lại. Khi quét từ trái sang phải, các thao tác cập nhật và truy vấn sẽ diễn ra trên chiều còn lại.

Nếu truy vấn có thể hiệu (dạng prefix sum), dùng cây Fenwick (BIT) hoặc segment tree; nếu không, dùng phân chia và chinh phục (CDQ divide and conquer, nhưng ở đây không đề cập).

Một cách khác là nhìn bài toán dưới góc độ dãy số: quét theo điểm kết thúc \(r=1\cdots n\), duy trì cấu trúc dữ liệu cho các điểm bắt đầu \(l\), tức là quét một chiều, cấu trúc dữ liệu duy trì chiều còn lại.

Độ phức tạp thường là \(O((n+m)\log n)\).

Đếm điểm trong hình chữ nhật 2D

Cho một dãy số độ dài \(n\), có \(m\) truy vấn, mỗi truy vấn hỏi có bao nhiêu phần tử trong đoạn \([l,r]\) có giá trị thuộc \([x,y]\).

Bài toán này gọi là "đếm điểm trong hình chữ nhật 2D". Thực chất là đếm số điểm trong một hình chữ nhật trên mặt phẳng.

Cách đơn giản nhất là dùng quét + cây Fenwick (BIT).

Vì đây là bài toán tĩnh 2D, ta dùng quét để chuyển thành bài toán động 1D, rồi dùng cấu trúc dữ liệu cho dãy số.

Trước hết, rời rạc hóa các truy vấn, dùng BIT duy trì số lượng phần tử theo giá trị. Với mỗi truy vấn \(l, r\), khi quét đến \(l-1\) thì đếm số phần tử trong \([x,y]\) là \(a\), khi quét đến \(r\) thì đếm được \(b\), đáp án là \(b-a\).

Bài tập ví dụ

LuoGu P2163 [SHOI2007] Nỗi phiền của người làm vườn

Đầu tiên rời rạc hóa. Gọi \(ans_{x, y}\) là số điểm trong hình chữ nhật có góc dưới trái \((0,0)\), góc trên phải \((x,y)\). Đáp án truy vấn là \(ans_{c, d} - ans_{a - 1, d} - ans_{c, b - 1} + ans_{a - 1, b - 1}\).

Mã mẫu 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <algorithm>
#include <iostream>

int n, m;
int x[500010], y[500010], ans[500010];
int ax[1500010], ay[1500010], tx, ty;  // 离散化

struct query {
  int a, b, c, d;
} q[500010];  // 保存查询操作方便离散化

struct ope {
  int type, x, y, id;

  ope(int type = 0, int x = 0, int y = 0, int id = 0) {
    this->type = type, this->x = x, this->y = y, this->id = id;
  }

  bool operator<(const ope& rhs) const {
    if (x == rhs.x) return type < rhs.type;
    return x < rhs.x;
  }
};

ope op[2500010];
int tot;  // 操作总数

int sum[1500010];  // 树状数组

int lowbit(int x) { return x & (-x); }

void add(int x, int k) {
  while (x <= 1500000) {
    sum[x] = sum[x] + k;
    x = x + lowbit(x);
  }
}

int getsum(int x) {
  int ret = 0;
  while (x > 0) {
    ret = ret + sum[x];
    x = x - lowbit(x);
  }
  return ret;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m, tx = n, ty = n;
  for (int i = 1; i <= n; i++) cin >> x[i] >> y[i], ax[i] = x[i], ay[i] = y[i];
  for (int i = 1, l, r; i <= m; i++) {
    cin >> q[i].a >> q[i].b >> q[i].c >> q[i].d;
    ax[++tx] = q[i].a, ay[++ty] = q[i].b, ax[++tx] = q[i].c, ay[++ty] = q[i].d;
  }
  std::sort(ax + 1, ax + tx + 1), std::sort(ay + 1, ay + ty + 1);
  tx = std::unique(ax + 1, ax + tx + 1) - ax - 1;
  ty = std::unique(ay + 1, ay + ty + 1) - ay - 1;
  for (int i = 1; i <= n; i++) {
    x[i] = std::lower_bound(ax + 1, ax + tx + 1, x[i]) - ax;
    y[i] = std::lower_bound(ay + 1, ay + ty + 1, y[i]) - ay;
    op[++tot] = ope(0, x[i], y[i], i);  // 加点操作
  }
  for (int i = 1; i <= m; i++) {
    q[i].a = std::lower_bound(ax + 1, ax + tx + 1, q[i].a) - ax;
    q[i].b = std::lower_bound(ay + 1, ay + ty + 1, q[i].b) - ay;
    q[i].c = std::lower_bound(ax + 1, ax + tx + 1, q[i].c) - ax;
    q[i].d = std::lower_bound(ay + 1, ay + ty + 1, q[i].d) - ay;
    op[++tot] = ope(1, q[i].c, q[i].d, i);  // 将查询差分
    op[++tot] = ope(1, q[i].a - 1, q[i].b - 1, i);
    op[++tot] = ope(2, q[i].a - 1, q[i].d, i);
    op[++tot] = ope(2, q[i].c, q[i].b - 1, i);
  }
  std::sort(op + 1, op + tot + 1);  // 将操作按横坐标排序，且优先执行加点操作
  for (int i = 1; i <= tot; i++) {
    if (op[i].type == 0)
      add(op[i].y, 1);
    else if (op[i].type == 1)
      ans[op[i].id] += getsum(op[i].y);
    else
      ans[op[i].id] -= getsum(op[i].y);
  }
  for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
  return 0;
}
LuoGu P1908 Đếm số nghịch thế

Đúng vậy, đếm số nghịch thế cũng có thể dùng tư tưởng quét. Chuyển bài toán thành: duyệt từ cuối về đầu, với mỗi vị trí \(i\), đếm số phần tử trong \([i+1,n]\) nhỏ hơn \(a_i\). Vì giá trị có thể lớn, cần rời rạc hóa. Duyệt từ cuối về đầu, mỗi lần cập nhật BIT, rồi đếm số phần tử nhỏ hơn \(a_i\) (tức là số nghịch thế của \(a_i\)). Có thể dùng BIT hoặc segment tree để cập nhật và truy vấn.

Mã mẫu 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <algorithm>
#include <iostream>
using ll = long long;
using namespace std;

struct node {
  ll data;
  ll num;
} f[500010];

ll n, ans, a[500010];

bool cmp(node a, node b) {
  if (a.data == b.data) {
    return a.num < b.num;
  }
  return a.data < b.data;
}

ll sum[500010];

int lowbit(int x) { return x & (-x); }

void add(int x, int k) {
  while (x <= n) {
    sum[x] = sum[x] + k;
    x = x + lowbit(x);
  }
}

int getsum(int x) {
  int ret = 0;
  while (x > 0) {
    ret = ret + sum[x];
    x = x - lowbit(x);
  }
  return ret;
}

int main() {
  cin >> n;
  for (ll i = 1; i <= n; i++) {
    cin >> f[i].data;
    f[i].num = i;
  }
  sort(f + 1, f + 1 + n, cmp);
  for (int i = 1; i <= n; i++) {
    a[f[i].num] = i;
  }
  for (ll i = n; i > 0; i--) {
    ans += getsum(a[i]);
    add(a[i], 1);
  }
  cout << ans;
  return 0;
}
LuoGu P1972 [SDOI2009] Chuỗi hạt của HH

Tóm tắt: Cho một dãy số, nhiều truy vấn hỏi trong đoạn \([l,r]\) có bao nhiêu số khác nhau.

Có thể suy luận tính chất, rồi dùng quét theo điểm kết thúc, cấu trúc dữ liệu duy trì điểm bắt đầu, hoặc chuyển về bài toán đếm điểm trong hình chữ nhật 2D.

Với mỗi \(a_i\), gọi \(pre_i\) là vị trí xuất hiện trước đó của \(a_i\) (nếu chưa từng xuất hiện thì \(pre_i=0\)). Theo đề, mỗi số chỉ tính một lần trong đoạn, nên chỉ cần đếm số \(pre_x \le l-1\) trong đoạn \([l,r]\).

Bài toán trở thành: cho dãy \(pre\), nhiều truy vấn hỏi trong đoạn \([l,r]\) có bao nhiêu \(pre_i \le l-1\).

Xem \(pre_i\) là điểm trên mặt phẳng: hoành độ \(i\), tung độ \(pre_i\), mỗi truy vấn là đếm số điểm trong hình chữ nhật có góc dưới trái \((l,0)\), góc trên phải \((r,l-1)\).

Vì truy vấn có thể hiệu, ta tách thành hai hình chữ nhật: \((0,0)-(r,l-1)\) trừ \((0,0)-(l-1,l-1)\). Như vậy dễ dùng quét.

Mỗi thao tác \(O(\log n)\), tổng \(O((n+m)\log n)\).

Mã mẫu 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <algorithm>
#include <iostream>

int n, m, a[1000010], ans[1000010];
int pre[1000010], lst[1000010];  // 处理 pre

struct ope {
  int type, x, y, id;

  ope(int type = 0, int x = 0, int y = 0, int id = 0) {
    this->type = type, this->x = x, this->y = y, this->id = id;
  }

  bool operator<(const ope& rhs) const {
    if (x == rhs.x) return type < rhs.type;
    return x < rhs.x;
  }
};

ope op[2500010];
int tot;  // 操作总数

int sum[1000010];  // 树状数组

int lowbit(int x) { return x & (-x); }

void add(int x, int k) {
  x++;  // 位置 0 也要进行修改，所以树状数组下标均加 1
  while (x <= n) {
    sum[x] = sum[x] + k;
    x = x + lowbit(x);
  }
}

int getsum(int x) {
  x++;
  int ret = 0;
  while (x > 0) {
    ret = ret + sum[x];
    x = x - lowbit(x);
  }
  return ret;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pre[i] = lst[a[i]], lst[a[i]] = i;  // 处理 pre
    op[++tot] = ope{0, i, pre[i], i};   // 加点操作
  }
  cin >> m;
  for (int i = 1, l, r; i <= m; i++) {
    cin >> l >> r;
    op[++tot] = ope{1, r, l - 1, i};  // 将查询差分
    op[++tot] = ope{2, l - 1, l - 1, i};
  }
  std::sort(op + 1, op + tot + 1);  // 将操作按横坐标排序，且优先执行加点操作
  for (int i = 1; i <= tot; i++) {
    if (op[i].type == 0)
      add(op[i].y, 1);
    else if (op[i].type == 1)
      ans[op[i].id] += getsum(op[i].y);
    else
      ans[op[i].id] -= getsum(op[i].y);
  }
  for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
  return 0;
}

Bài tập luyện tập

Tóm lại, tư tưởng chính của đếm điểm trong hình chữ nhật 2D là: dùng cấu trúc dữ liệu duy trì một chiều, quét qua chiều còn lại.

Tài liệu tham khảo

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply