Luogu 🟠 P1496 火烧赤壁

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P1496 火烧赤壁

Problem Statement

題意摘要

給你 $n$ 個燃燒區間 $[a, b)$，要你求出所有燃燒位置的總長度，也就是這些半開區間的聯集長度。

Constraints

資料範圍

• $1 \le n \le 2 \times 10^4$
• $-2^{31} \le a < b < 2^{31}$
• 區間是左閉右開 $[a, b)$
• 答案小於 $2^{31}$

---

思路：區間聯集長度

方法一：合併區間（貪心 + 排序）

題意為：給很多段 $[a,b)$，它們可能重疊、可能相接，問「合起來總共覆蓋了多長」。
這是經典的 56. Merge Intervals 問題。

可以先排序，然後從左到右把能接在一起的段合併。掃描時只需要記住「目前這一段合併後的右端點在哪」。當看到下一段的左端點時：

• 如果它在目前右端點的右邊，說明前一段結束了，開始新段。
• 否則就是有重疊或剛好接上，把右端點更新成更大的那個。

正確性證明

將所有區間依左端點排序後，由左到右掃描，維護「目前合併後的覆蓋段」。

• 不變量：掃描到第 $k$ 個排序後區間時，「目前合併後的覆蓋段」恰好等於前 $k$ 個區間的聯集，並且這個聯集可以表示成若干個互不相交且依序排列的區間；其中最後一段的右端點，就是我們維護的「目前右端點」。
• 初始化：第一個區間直接成為目前覆蓋段，不變量成立。
• 維護：考慮下一個區間 $[l,r)$：
  • 若 $l$ 在目前右端點右側（$l > R$），則它與既有聯集完全分離（注意半開區間下，$l=R$ 代表「剛好接上」仍屬連成一段），因此必須開啟新段。此時聯集變成「舊聯集 + 新區間」，不變量仍成立。
  • 否則 $l \le R$，新區間與最後一段有重疊或相接，聯集的最後一段會延伸到 $\max(R, r)$，只需把右端點更新成較大者即可；其餘已完成的段不受影響，不變量仍成立。
• 終止：掃描完所有區間後，得到的若干段即為全部區間的聯集分解。因為它們互不重疊，總長度等於各段長度和，也就是答案。

複雜度分析

• 時間複雜度：$\mathcal{O}(n \log n)$（排序主導，後續線性掃描合併）
• 空間複雜度：$\mathcal{O}(n)$（排序後存放區間；若原地排序並只維護目前段，額外工作空間可視作 $\mathcal{O}(1)$）

方法二：離散化結合差分陣列（數線掃描思維）

除了合併，也可以換個想法：把整條數線切成很多左閉右開的小段 $[x_i, x_{i+1})$，判斷每小段「有沒有被蓋到」，把有被蓋到的小段長度加總。

為什麼可以切成小段來判斷覆蓋？這樣做的正確性依據是什麼？

因為狀態只會在「某段的起點或終點」改變，因此對於每個小段內部來說，狀態是一樣的。只有可能是「整段都被蓋到」或「整段都沒被蓋到」，不會出現「半段被蓋到、半段沒被蓋到」的情況。

為什麼要切成「左閉右開 $[x_i, x_{i+1})$」的小段？

這是為了讓切出來的小段「彼此沒有重疊」，省去了一些麻煩的判斷問題。
切成左閉右開後，相鄰兩段只會在端點碰到，但端點不算進右邊，所以兩段不重疊，加總長度不會重複。

在切分成若干小段後，我們需要一個辦法來處理「哪些小段被蓋到」，這等同對於一個連續的區間做加法操作，直接維護有效率問題，可以使用差分陣列來維護：

• 對每個區間 $[a,b)$，在 $a$ 的位置 +1、在 $b$ 的位置 -1，表示「從這裡開始多蓋一層 / 到這裡少蓋一層」。
• 最後對差分陣列做前綴和，就能得到每個小段目前被蓋了幾層；只要層數 $>0$ 就代表這段被蓋到。

差分技巧的本質優勢

傳統上差分常用於連續陣列。此處雖然座標不連續，但離散化後的索引讓我們能用一個小陣列來模擬「事件發生點」，後續掃描時再把相鄰座標的實際距離還原成貢獻長度。這是將「連續數線問題」壓縮到「離散事件點」上的標準技巧。

延伸思考

如果題目改成求「被至少覆蓋兩次以上的總長度」，該如何修改差分與掃描的判斷條件？

複雜度分析

• 時間複雜度：$\mathcal{O}(n \log n)$（收集與排序所有端點是主要成本，後續掃描為線性）
• 空間複雜度：$\mathcal{O}(n)$（端點集合、離散映射表以及差分陣列的大小皆與端點數成正比）

類似題目

• 56. Merge Intervals
• P1884 [USACO12FEB] Overplanting S 二維版本

---

Code

方法一：合併區間

def solve():  #  Merge Interval
    q = int(input())
    intervals = [tuple(map(int, input().split())) for _ in range(q)]
    intervals.sort()

    merged = []
    for l, r in intervals:
        if not merged or l > merged[-1][1]:
            merged.append([l, r])
        else:
            merged[-1][1] = max(merged[-1][1], r)

    ans = sum(r - l for l, r in merged)
    print(ans)

if __name__ == "__main__":
    solve()

方法二：離散化 + 差分

from itertools import pairwise

def solve():
    q = int(input())
    queries = [tuple(map(int, input().split())) for _ in range(q)]

    # 離散化
    Xs = set()
    for l, r in queries:  # [l, r)
        Xs.add(l)
        Xs.add(r)
    Xs = sorted(Xs)
    mp = {x: i for i, x in enumerate(Xs)}
    m = len(Xs)

    # 差分
    diff = [0] * (m + 1)
    for l, r in queries:
        diff[mp[l]] += 1
        diff[mp[r]] -= 1

    ans = s = 0
    for i, (a, b) in enumerate(pairwise(Xs)):
        s += diff[i]
        if s > 0:
            ans += b - a

    print(ans)

if __name__ == "__main__":
    solve()