掃描線

引入

掃描線一般運用在圖形上面，它和它的字面意思十分相似，就是一條線在整個圖上掃來掃去，它一般被用來解決圖形面積，周長，以及二維數點等問題。

Atlantis 問題

題意

在二維座標系上，給出多個矩形的左下以及右上座標，求出所有矩形構成的圖形的面積。

解法

根據圖片可知總面積可以直接暴力即可求出面積，如果數據大了怎麼辦？這時就需要講到 掃描線 算法。

過程

現在假設我們有一根線，從下往上開始掃描：

• 如圖所示，我們可以把整個矩形分成如圖各個顏色不同的小矩形，那麼這個小矩形的高就是我們掃過的距離，那麼剩下了一個變量，那就是矩形的長一直在變化。
• 我們的線段樹就是為了維護矩形的長，我們給每一個矩形的上下邊進行標記，下面的邊標記為 1，上面的邊標記為 -1，每遇到一個矩形時，我們知道了標記為 1 的邊，我們就加進來這一條矩形的長，等到掃描到 -1 時，證明這一條邊需要刪除，就刪去，利用 1 和 -1 可以輕鬆的到這種狀態。
• 還要注意這裏的線段樹指的並不是線段的一個端點，而指的是一個區間，所以我們要計算的是 \(r+1\) 和 \(r-1\)。
• 需要 離散化。

實現

代碼實現

#include <algorithm>
#include <cstdio>
#include <cstring>
#define 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;
}

練習

• 「POJ1151」Atlantis

• 「POJ1177」Picture

• 「POJ3832」Posters

• 洛谷 P1856[IOI1998][USACO5.5] 矩形周長 Picture

B 維正交範圍

B 維正交範圍指在一個 B 維直角座標系下，第 \(i\) 維座標在一個整數範圍 \([l_i,r_i]\) 間，內部的點集。

一般來説，一維正交範圍簡稱區間，二維正交範圍簡稱矩形，三維正交範圍簡稱立方體（我們常説的二維數點就是二維正交範圍）。

對於一個靜態的二維問題，我們可以使用掃描線掃一維，數據結構維護另一維。 在掃描線從左到右掃的過程中，會在數據結構維護的那一維上產生一些修改與查詢。 如果查詢的信息可差分的話直接使用差分，否則需要使用分治。差分一般用樹狀數組和線段樹維護，但因為樹狀數組好寫而且常數小，所以大部分人會選擇用樹狀數組來維護。分治一般是 CDQ 分治（但是這裏不涉及分治）。

另一種比較容易理解的看待問題的角度是站在序列角度，而不站在二維平面角度。如果我們這樣看待問題，則掃描線實際上是枚舉了右端點 \(r=1\cdots n\)，維護一個數據結構，支持查詢對於當前的 \(r\)，給定一個值 \(l\)，\(l\) 到 \(r\) 的答案是什麼。即掃描線掃詢問右端點，數據結構維護所有左端點的答案，或者説遍歷一維，數據結果維護另一維。

複雜度一般為 \(\mathcal O((n+m)\log n)\)。

二維數點

給一個長為 \(n\) 的序列，有 \(m\) 次查詢，每次查區間 \([l,r]\) 中值在 \([x,y]\) 內的元素個數。

這個問題就叫做二維數點。我們可以發現等價於我們要查詢一個二維平面上矩形內的點的數量和。這裏講一下這個問題最簡單的處理方法，掃描線 + 樹狀數組。

很顯然，這個問題是一個靜態的二維問題，我們通過掃描線可以將靜態的二維問題轉換為動態的一維問題。維護動態的一維問題就使用數據結構維護序列，這裏可以使用樹狀數組。

先將所有的詢問離散化，用樹狀數組維護權值，對於每次詢問的 \(l\) 和 \(r\)，我們在枚舉到 \(l-1\) 時統計當前位於區間 \([x,y]\) 內的數的數量 \(a\)，繼續向後枚舉，枚舉到 \(r\) 時統計當前位於區間 \([x,y]\) 內的數的數量 \(b\)，\(b-a\) 即為該次詢問的答案。

可以用 洛谷 P2163[SHOI2007] 園丁的煩惱 這道題進行練習。

例題

洛谷 P1908 逆序對

沒錯，逆序對也可以用掃描線的思維來做。考慮將求逆序對的個數轉化為從後向前枚舉每個位置 \(i\)，求在區間 \([i+1,n]\) 中，大小在區間 \([0,a_i]\) 中的點的個數。題目中數據範圍為 \(10^9\)，很顯然要先進行離散化，我們可以考慮從後向前遍歷數組，每次遍歷到一個數時更新數組數組（線段樹），之後統計當前一共有多少個數小於當前枚舉的數，因為我們是從後向前遍歷的，所以比當前值小的數的個數就是他的逆序對的個數，可以用樹狀數組或線段樹進行單點修改和區間查詢。

代碼

#include <bits/stdc++.h>
#define ll long long
using namespace std;

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

ll n, c[5000001], ans, a[5000001];

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

ll lowbit(ll i) { return i & (-i); }

ll sum(ll x) {
  ll s = 0;
  for (; x > 0; x -= lowbit(x)) {
    s += c[x];
  }
  return s;
}

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 += sum(a[i]);
    for (ll j = a[i]; j <= n; j += lowbit(j)) {
      c[j]++;
    }
  }
  cout << ans;
  return 0;
}

洛谷 P1972 [SDOI2009] HH 的項鍊

簡要題意：給定一個長為 \(n\) 的序列，\(m\) 次查詢區間中有多少不同的數。

這類問題我們可以考慮推導性質，之後使用掃描線枚舉所有右端點，數據結構維護每個左端點的答案的方法來實現，我們也可以將問題轉換到二維平面上，變為一個矩形查詢信息的問題。

在這道題中，對於每個位置 \(i\)，考慮預處理出 \(i\) 左邊離 \(i\) 最近的 \(j\) 滿足 \(a_i=a_j\)，用一個數組記錄，即 \(pre_i=j\)。

然後查詢區間中的不同數，我們可以只把每個數在區間中最後一次出現時統計進去。

若這個數在當前區間中是第一次出現，那麼這個數肯定滿足 \(pre_i < l\)。如果不是第一次出現，那麼 \(l \le pre_i\)。這樣問題就轉變成了求區間 \([l,r]\) 中，滿足 \(pre_i < l\) 的 \(i\) 的個數。

我們可以考慮差分，將區間 \([l,r]\) 差分為前綴 \([1,r]\) 減去前綴 \([1,l-1]\)。考慮將詢問離線處理，假設有一個詢問是對於區間 \([l,r]\) 的，我們在 \(l-1\) 位置上和 \(r\) 位置上分別記錄一下，答案為在 \(r\) 處記錄的 \(pre_i < l\) 的個數減去在 \(l-1\) 處記錄的 \(pre_i < l\) 的 \(i\) 的個數。

每次查詢可以用值域線段樹或值域樹狀數組來維護，注意一個位置上可能有多個詢問，但總共的查詢次數是 \(m\) 次。總時間複雜度 \(\mathcal O((n+m)\log n)\)。

代碼

#include <bits/stdc++.h>
#define ls x << 1
#define rs x << 1 | 1
#define N 1000010
using namespace std;

struct node {
  int l, r, ans;
} q[N];

struct t {
  int num, s;
};

vector<t> p[N];
int n, a[N], m, now[N];
int siz[N << 2];

void update(int x, int l, int r, int ad) {
  if (l == r && l == ad) {
    siz[x]++;
    return;
  }
  int mid = l + r >> 1;
  if (ad <= mid) {
    update(ls, l, mid, ad);
  } else {
    update(rs, mid + 1, r, ad);
  }
  siz[x] = siz[ls] + siz[rs];
}

int query(int x, int l, int r, int L, int R) {
  if (l >= L && r <= R) {
    return siz[x];
  }
  int mid = l + r >> 1;
  int res = 0;
  if (L <= mid) {
    res += query(ls, l, mid, L, R);
  }
  if (R > mid) {
    res += query(rs, mid + 1, r, L, R);
  }
  return res;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    p[l - 1].push_back(t{i, -1});
    p[r].push_back(t{i, 1});
    q[i] = node{l, r, 0};
  }
  for (int i = 1; i <= n; i++) {
    update(1, 0, n, now[a[i]]);
    now[a[i]] = i;
    for (auto x : p[i]) {
      int num = x.num;
      q[num].ans += x.s * query(1, 0, n, 0, q[num].l - 1);
    }
  }
  for (int i = 1; i <= m; i++) {
    printf("%d\n", q[i].ans);
  }
  return 0;
}

例題

• 洛谷 P8593「KDOI-02」一個彈的投 逆序對的應用。

• AcWing 4709. 三元組 上題的弱化版，同樣為逆序對的應用。

• 洛谷 P8773[藍橋杯 2022 省 A] 選數異或 HH 的項鍊魔改版。

• 洛谷 P8844[傳智杯 #4 初賽] 小卡與落葉 樹上問題轉序列問題然後進行二維數點。

總而言之，二維數點的主要思路就是數據結構維護一維，然後枚舉另一維。

參考資料

• https://www.cnblogs.com/yangsongyi/p/8378629.html

• https://blog.csdn.net/riba2534/article/details/76851233

• https://blog.csdn.net/winddreams/article/details/38495093

• https://dregen-yor.cf/2022/10/01/sao-miao-xian

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用