【C++】競程筆記（一維掃描線）
===
[TOC]
程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。
數線問題
---
例題（APCS 2016 年 3 月第三題）：https://zerojudge.tw/ShowProblem?problemid=b966
測資加強版：https://zerojudge.tw/ShowProblem?problemid=f855
```cpp=
#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 跑看看：
```
5
160 180
150 200
280 300
300 330
190 210
```
排序後：(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。
總之解題思路就是：
1. 用 pair 資料結構
2. 排序 pair 的 first
3. 初始化第一條線段的左右界（`L`、`R`）為 `vector<pair<int, int>> seg`（`l = seg[0].first` 跟 `r = seg[0].second`）。
4. 用迴圈跑重疊或相鄰的區間（`seg[i].first <= r`，`i = 1`），以 `max()` 更新 `R`，然後繼續跳下一個線段。
5. 不重疊或相鄰就直接計算長度（`R - L`），繼續前往下個線段。
6. 由於重疊或相鄰的區間在計算時只有 `max()`（因為題目要求不要計算重複的重疊區間），最後要記得計算他們的長度。
不過這是我本人的解法，不算是用掃描線去解的，以下是 NTUCPC Guide 的解法（掃描線）：
```cpp=
// 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。
那通常處理優先順序會如下所示（這部分依據題目要求可自行調整）：
1. 加入事件（start）先於移除事件（end）。
2. 高度高的房子先處理（如：高度從高到低排序）。
3. 起點 vs 起點：高的先；終點 vs 終點：低的先。
### 複雜的事件
---
複雜的事件就是「區間包含查詢」問題，如包含點的線段數問題。
習題練習
---
1. b526. 先別管這個了，你聽過微鼓勵嗎？：https://zerojudge.tw/ShowProblem?problemid=b526
```cpp=
#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;
}
```
以上是由範例測資所畫出的圖。
先預設一個起始狀態，假設一開始全部人都是站著的。
那首先第一個區間微鼓勵下去之後，編號 1 ~ 3 的人全都蹲著。
第二個區間做完微鼓勵之後，1 ~ 2 維持不變，編號 3 站起，4 ~ 5 蹲下。
第三個區間做完之後，1 ~ 2 跟 4 ~ 5 站起，僅 3 號蹲下。
所以全部做完後，有 4 個人站著。
在這支程式中有個很重要的解題思路，就是我們不需要去紀錄每個人的最終狀態，而是要紀錄「哪些區間被反轉」。
具體步驟如下所示：
1. 將每次操作紀錄為區間反轉，如：微鼓勵 `[l, r]` → 在 l 處 +1，r+1 處 -1。
2. 對所有點排序、掃描，計算每段區間共幾次反轉。
3. 如果該段反轉次數是偶數，則狀態不變；奇數則反轉（站著變蹲下）。
4. 統計站著的總人數。
在這支程式中：
- 差分用來記錄變化量。（n 太大了，所以只要記錄有變化的就好）
- cur 變數用來記錄目前區間的累計反轉次數
- prev 作為目前區間的起始位置（題目要求從編號 1 開始）
- standing 紀錄站著的人次
`for (auto &[pos, delta] : diff)` 做結構化綁定。
`long long end = min(pos, n + 1);` 表示目前區間的右端點，也是區間的結束位置（這個點是空心的，不含在內）。
`if (cur % 2 == 0 && prev < end)` 因為預設的狀態就是站著的，所以 `cur % 2 == 0` 表示反轉狀態不變，一樣站著，`prev < end` 為了避免處理長度為 0 的區間。
那題目要求站著的人數，所以接下來就 `standing += end - prev;`，表示這段區間的人都是站著的。
Sign in with Wallet
Connect another wallet