【C++】競程筆記（一維掃描線）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

數線問題

例題（APCS 2016 年 3 月第三題）：https://zerojudge.tw/ShowProblem?problemid=b966

測資加強版：https://zerojudge.tw/ShowProblem?problemid=f855

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    vector<pair<int, int>> seg(N);
    for (int i = 0; i < N; ++i) {
        cin >> seg[i].first >> seg[i].second;
    }

    sort(seg.begin(), seg.end());

    int total_length = 0;
    int l = seg[0].first;
    int r = seg[0].second;
    for (int i = 1; i < N; ++i) {
        if (seg[i].first <= r) {
            // 重疊或相鄰
            r = max(r, seg[i].second);
        } else {
            // 不重疊，計算前一段的長度並前往下一個線段
            total_length += (r - l);
            l = seg[i].first;
            r = seg[i].second;
        }
    }
    // 加上最後一段的長度
    total_length += (r - l);

    cout << total_length << '\n';
    return 0;
}

拿範例測資 1 跑看看：

排序後：(150, 200)、(160, 180)、(190, 210)、(280, 300)、(300, 330)。

合併過程：

(150, 200) 和 (160, 180) 重疊，還是 (150, 200)，因為 200 最大。
(150, 200) 和 (190, 210) 重疊，更新為 (150, 210)。
(150, 210) 和 (280, 300) 不重疊，計算 (150, 210) 長度 60，從 (280, 300) 繼續開始前往下一個線段。
(280, 300) 和 (300, 330) 相鄰，更新為 (280, 330)。

最後計算 (280, 330) 長度 50。

總長度 = 60 + 50 = 110。

總之解題思路就是：

用 pair 資料結構
排序 pair 的 first
初始化第一條線段的左右界（L、R）為 vector<pair<int, int>> seg（l = seg[0].first 跟 r = seg[0].second）。
用迴圈跑重疊或相鄰的區間（seg[i].first <= r，i = 1），以 max() 更新 R，然後繼續跳下一個線段。
不重疊或相鄰就直接計算長度（R - L），繼續前往下個線段。
由於重疊或相鄰的區間在計算時只有 max()（因為題目要求不要計算重複的重疊區間），最後要記得計算他們的長度。

不過這是我本人的解法，不算是用掃描線去解的，以下是 NTUCPC Guide 的解法（掃描線）：

// from NTUCPC Guide
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
    vector<pii> events;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        events.emplace_back(pii(l, 1));
        events.emplace_back(pii(r, -1));
        // 1 代表左端點，-1 代表右端點
        // 也就是走到那個點時，包住當前位置線段數的改變量
    }
    sort(events.begin(), events.end());
    int cur = 0; // 包住當前位置的線段數
    int ans = 0;
    int lst = -1; // 上一個碰到的端點
    for (auto [x, diff] : events) {
        // 如果前面那一段的是有被包住的，要加上那一段的長度
        if (cur > 0) ans += x - lst;
        cur += diff;
        lst = x;
    }
    cout << ans << "\n";
}

掃描線與事件

這種想像自己在走的方法稱為掃描線，就是想像有一條直線掃過去，你就是那條直線。
from NTUCPC Guide
掃描對象是很單純的一個序列（一些格子）配上一些區間，或者一條數線配上一些線段，然後很單純的左往右掃，這種題目的作法框架基本上都差不多，首先先找出你關心的當下狀態，然後看看狀態什麼時候會發生改變，狀態改變的事情就被稱為事件，把事件按照發生時間點（通常就是座標）排序後，就可以好好摸擬掃描的過程，如果座標範圍不大，也可以直接開一個長度是 $C$ 的陣列來直接儲存每個整數時間點發生的事件，並一一枚舉所有整數時間點。
from NTUCPC Guide

精簡一下：

掃描線是一種想像自己是條線、從左到右（也可以由下往上）掃過整個序列或數線的解法。

它的核心概念是觀察「狀態」何時改變，並將這些變化視為「事件」。將所有事件依照發生時間（或座標）排序後，就能模擬整個掃描過程。若座標範圍不大，也可用長度為 $C$ 的陣列來記錄每個整數時間點的事件並逐一處理。

那至於啥是事件呢？像是線段的端點（起始點和終點）是事件的一種。

掃描的起點

用掃描線要有起始狀態，如於線段覆蓋的程式中 lst = -1，假設起點為 -1，起點狀態包住目前的線段數為 0。通常只要挑所有端點左邊當作起點即可。

而在對序列掃描時，可以自己加一個 index 是 0 的位置當起點。
from NTUCPC Guide

邊界條件

在線段長度覆蓋的問題中，一線段的 $[l, r]$ 的意思即為數線上 $[l, r]$ 的範圍，只關心到長度，而單一點的狀態不重要，只要在乎每個時間點之間的狀態。進入區間的時間是走過 $l$ 以後，離開區間的時間是走過 $r$ 以後。

同時發生的事件

當掃描線掃到某特定位置上，有不只一個事件要處理時，就會發生同時發生的事件。

假設有兩棟房子：

A：從 x=2 到 x=5，高度 10。
B：從 x=2 到 x=6，高度 15。

那通常處理優先順序會如下所示（這部分依據題目要求可自行調整）：

加入事件（start）先於移除事件（end）。
高度高的房子先處理（如：高度從高到低排序）。
起點 vs 起點：高的先；終點 vs 終點：低的先。

複雜的事件

複雜的事件就是「區間包含查詢」問題，如包含點的線段數問題。

習題練習

b526. 先別管這個了，你聽過微鼓勵嗎？：https://zerojudge.tw/ShowProblem?problemid=b526

#include <iostream>
#include <map>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    int m;
    cin >> n >> m;

    //  pos      , delta
    map<long long, int> diff;

    for (int i = 0; i < m; ++i) {
        long long l, r;
        cin >> l >> r;
        // 區間加值
        diff[l] += 1;
        diff[r + 1] -= 1;
    }

    long long cur = 0; // 目前區間的「累積反轉次數」
    long long prev = 1; // 目前區間的起始位置（編號 1 開始）
    long long standing = 0; // 站著次數

    for (auto &[pos, delta] : diff) {
        if (pos > n + 1) break;

        long long end = min(pos, n + 1);
        if (cur % 2 == 0 && prev < end) { // 反轉次數是偶數就代表狀態沒變化
            // 當前區間是站著狀態，加總站立人數
            standing += end - prev;
        }

        cur += delta; // 累計該位置的反轉次數, 更新目前的狀態。
        prev = pos; // 更新起點
    }

    // 若最後一段尚未結束，需特別補處理
    if (prev <= n && cur % 2 == 0) {
        standing += n - prev + 1;
    }

    cout << standing << '\n';
    return 0;
}