線段覆蓋長度 (APCS 2016-03 中高級) 的題解

前置知識

這題會用到兩個現成的技巧，下面的講解直接把它們當成已知，沒讀過的先讀：

  • 前綴和與差分：NTUCPC Guide〈前綴和與差分〉——要帶走的一句話是「在 d[l] 加 \(1\)、d[r] 減 \(1\)，再做一次前綴和，就等於把 \([l, r)\) 這一整段每格加 \(1\)」。
  • 把 pair 排序：語法書 11.5（vector<pair<int,int>> 丟給 sort，先比 first）。

延伸閱讀（讀完題解再看也可以）：NTUCPC Guide〈一維掃描線〉的例題之一就是本題；吳邦一《AP325》第 4 章「掃描線演算法」的 P-4-11 線段聯集也是本題（教材 PDF 第 129～131 頁；Python 版第 4 章（II）），兩種做法都有。

簡潔題意

數線上 \(N\) 條線段 \([L, R]\)（\(0 \le L \le R < 10^7\)、\(N < 10000\)），求它們聯集的總長度——重疊的部分只算一次。長度是 \(R - L\)，所以一個點（\(L = R\)）的長度是 \(0\)。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(30\) 分）：\(N < 100\)，\(0 \le L, R < 1000\)，線段互不重疊。
  • 子題組 2（\(40\) 分）：\(N < 100\)，\(0 \le L, R < 1000\)。
  • 子題組 3（\(30\) 分）：無額外限制。

先拿下 30 分：不重疊就直接加總

線段互不重疊時，聯集長度就是各線段長度相加：

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

int main() {
    int n;
    cin >> n;
    long long total = 0;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        total += r - l;        // 子題組 1 保證線段互不重疊：長度直接相加
    }
    cout << total << '\n';
    return 0;
}

範例 1 有重疊（\([150, 200]\) 整個包住 \([160, 180]\)），這份程式會印 140——範例 1 WA 是正常的，逐筆給分之下子題組 1 的 \(30\) 分穩穩到手。

從 30 分到 70 分：座標小就逐格標記

「長度」可以換個方式數：把數線切成一格一格的單位區段 \([x, x+1)\)，線段 \([L, R]\) 蓋住的正好是第 \(L, L+1, \dots, R-1\) 格，共 \(R - L\) 格——這也解釋了為什麼一個點長度是 \(0\)（一格都沒蓋到）。聯集長度就是「至少被一條線段蓋到的格子有幾格」，重疊自然只算一次。

座標 \(< 1000\) 時，開一個 covered[1000]，每條線段把自己蓋到的格子全部標成 true，最後數有幾格是 true：

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

bool covered[1000];                 // covered[x]：單位區段 [x, x+1) 有沒有被蓋到

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        for (int x = l; x < r; x++) covered[x] = true;   // 第 l 格到第 r-1 格
    }
    int total = 0;
    for (int x = 0; x < 1000; x++)
        if (covered[x]) total++;
    cout << total << '\n';
    return 0;
}

這個做法的運算量是「所有線段長度的總和」，跟座標範圍綁在一起。子題組 3 的座標到 \(10^7\)、線段近 \(10^4\) 條，最壞情況（每條都橫跨整條數線）要標記 \(10^{11}\) 次——本站實測約 \(2\) 秒，超過時限。下面兩種做法各從一個角度擺脫這個限制。

100 分做法一：差分

逐格標記慢在「一條線段要動 \(R - L\) 格」。差分正是為這件事而生：把「\([L, R)\) 每格加 \(1\)」換成只動兩格——d[L] 加 \(1\)、d[R] 減 \(1\)。全部線段都登記完之後，從左到右做一次前綴和，位置 \(x\) 的累積值就是「第 \(x\) 格被幾條線段蓋到」；大於 \(0\) 的格子數一數，就是答案。

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

const int MAX_C = 10000000;         // 座標 < 10^7
int d[MAX_C + 1];                   // 差分陣列：d[l]++、d[r]-- 代表第 l ~ r-1 格各加 1

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        d[l]++;
        d[r]--;
    }
    int total = 0, cover = 0;       // cover：目前這一格被幾條線段蓋到
    for (int x = 0; x < MAX_C; x++) {
        cover += d[x];              // 前綴和
        if (cover > 0) total++;     // 至少一條蓋到 → 這一格算進長度
    }
    cout << total << '\n';
    return 0;
}

每條線段只動兩格、前綴和掃一遍 \(10^7\) 格，運算量 \(O(N + 10^7)\)，本站實測約 \(0.03\) 秒；陣列 \(10^7\) 個 int 約 \(40\) MB，在 \(256\) MB 的限制內。

100 分做法二：排序後合併

另一個角度：讓運算量只跟 \(N\) 有關、跟座標範圍無關。把線段依左端點由小到大排序之後，從左往右一條一條併進「目前這一塊連通區間」\([curL, curR]\)：

  • 下一條的 \(L > curR\)：跟目前這塊接不上，先把 \(curR - curL\) 結算進答案，再用這條開新的一塊。
  • 否則它跟目前這塊有交集（或剛好接上），把 \(curR\) 拉到 \(\max(curR, R)\)。

為什麼只要跟「目前這一塊」比就夠？因為排過序，後面每條線段的左端點都不小於目前這條的左端點——它不可能跑回去碰到更早結算掉的那些塊。掃完之後別忘了把最後一塊也結算進去。

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

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> seg(n);              // first = 左端點、second = 右端點
    for (int i = 0; i < n; i++) cin >> seg[i].first >> seg[i].second;
    sort(seg.begin(), seg.end());               // pair 先比 first：依左端點排序

    long long total = 0;
    int curL = seg[0].first, curR = seg[0].second;   // 目前這一塊連通區間
    for (int i = 1; i < n; i++) {
        if (seg[i].first > curR) {              // 接不上：結算目前這塊、開新的一塊
            total += curR - curL;
            curL = seg[i].first;
            curR = seg[i].second;
        } else {                                // 有交集或剛好接上：往右延伸
            curR = max(curR, seg[i].second);
        }
    }
    total += curR - curL;                       // 最後一塊也要結算
    cout << total << '\n';
    return 0;
}

運算量由排序的 \(O(N \log N)\) 主導，記憶體只有 \(N\) 個 pair。\([280, 300]\) 和 \([300, 330]\) 這種剛好首尾相接的兩條，用 > 判斷會被併成一塊 \([280, 330]\)；寫成 >= 分成兩塊結算，長度一樣是 \(50\)，兩種都對。

兩種做法都是滿分。差分好寫、不用排序，但座標範圍決定陣列大小——座標上限若是 \(10^9\) 就開不下了；排序後合併跟座標範圍無關，是更通用的那一個。

測過再交：範例沒有「同一條線段出現兩次」

範例 1 已經蓋到不少情況：線段沒照順序給、\([150, 200]\) 包住 \([160, 180]\)、\([190, 210]\) 跨過 \(200\) 延伸出去、\([280, 300]\) 與 \([300, 330]\) 剛好相接；範例 2 是單獨一個點。沒蓋到的：重複的線段、單點夾在線段裡、座標頂到上限、以及一條線段同時包住好幾條。

輸入 正確輸出 這一筆在測什麼
3 ／ 0 10 ／ 2 3 ／ 5 9 10 一條線段包住後面兩條：合併時 \(curR\) 不能被短線段拉回來
3 ／ 4 8 ／ 4 8 ／ 6 6 4 兩條一模一樣、再加一個夾在中間的點：都不該多算
2 ／ 0 1 ／ 9999998 9999999 2 座標頂到 \(0\) 和 \(10^7 - 1\)：差分陣列的大小、迴圈的範圍
3 ／ 7 9 ／ 4 8 ／ 1 5 8 倒著給的三條鏈在一起成一大段 \([1, 9]\)：排序真的有排
2 ／ 5 5 ／ 5 7 2 單點跟線段同一個起點：排序後點排在前面、長度 \(0\) 不影響

五筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 每條長度直接相加，沒處理重疊：範例 1 印 140。
  • 長度算成 \(R - L + 1\)：範例 2 印 1。
  • 排序後只跟「上一條」的右端點比，沒有維護整塊的 \(curR\)：被包住的短線段會把右端點拉回來——範例 1 印 100。
  • 只排左端點、右端點沒跟著動（兩個陣列分開存、只 sort 其中一個）：端點配對整個亂掉——範例 1 印 180。
  • 忘了結算最後一塊：範例 1 印 60。
  • 差分陣列只開到 \(1000\)：子題組 1、2 全過，座標上 \(10^7\) 的子題組 3 六筆全掛。
  • 逐格標記硬上子題組 3：最壞情況本站實測約 \(2\) 秒，TLE。