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

🔗 P1904 天际线

Problem Statement

題目簡述

給定若干棟矩形建築，每棟建築用左邊界 ll、高度 hh、右邊界 rr 表示。
建築會互相重疊，從遠處觀察時，只能看到每個水平位置上的最高輪廓。
請依照座標由小到大的順序，輸出天際線發生高度變化的位置與變化後的高度。

Constraints

約束條件

  • 1≤n≤5×1031 \leq n \leq 5 \times 10^3，其中 nn 是建築數量
  • 1≤l,r,h≤1041 \leq l, r, h \leq 10^4

思路：從每個位置的最高高度到掃描線

天際線的本質，是找出「每個座標區間上，目前可見的最高建築高度」，然後只輸出高度發生改變的關鍵點即可。

方法一：座標枚舉

最直接的想法，是把每個整數座標位置的最高高度都記下來；但如果座標範圍很大，逐格更新會浪費時間。幸好本題的座標範圍只有 10410^4，因此即使每棟建築都逐格更新，O(n⋅W)O(n \cdot W) 的複雜度也只需要 10710^7 左右的運算量，還能接受。

直接建立一條高度陣列，對於每棟建築，將它覆蓋的所有整數位置都更新成「目前高度」與「該建築高度」的較大值。所有建築處理完後，再從左到右掃過高度陣列：只要目前高度和前一段高度不同，就代表天際線在此處發生轉折，需要輸出這個座標與新的高度。

區間端點

建築的右邊界不是覆蓋範圍的一部分。若一棟建築表示為左邊界、高度、右邊界，更新高度時只處理左邊界到右邊界前一格，這樣在右邊界處才會正確下降。

複雜度分析

  • 時間複雜度：O(n⋅W)\mathcal{O}(n \cdot W)，其中 nn 是建築數量，WW 是最大右邊界座標。
  • 空間複雜度：O(W)\mathcal{O}(W)，需要一條高度陣列記錄每個整數位置的最高高度。

方法二：掃描線 + 最大堆

更進一步可以發現，天際線只可能在建築的左邊界或右邊界改變。兩個相鄰邊界之間，覆蓋此區間的建築集合不會變，所以最高高度也不會變。

因此我們可以只掃描所有出現過的邊界座標。每到一個座標，就先把從這裡開始的建築加入「目前有效建築集合」；接著移除在此處以前結束的建築；最後集合中最高的建築高度，就是這個座標之後的可見高度。

由於每次都需要快速知道目前最高的有效建築，可以用最大堆維護高度。堆中同時保存建築的右邊界，方便在掃描到某個位置時，丟掉已經不再覆蓋目前位置的建築。

為什麼只掃左右邊界就夠？

在兩個相鄰邊界之間，沒有任何建築開始，也沒有任何建築結束；既然有效建築集合完全不變，最高高度也不可能改變。因此高度變化只可能發生在邊界座標。

正確性直覺

掃描到某個邊界後，堆中保留下來的都是右邊界仍在目前位置之後的建築，也就是仍然覆蓋目前位置的建築。堆頂代表其中最高者，所以得到的高度正是此處天際線的高度。若它與前一段不同，就輸出新的關鍵點。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n)，每棟建築至多入堆、出堆各一次，並排序所有邊界座標。
  • 空間複雜度：O(n)\mathcal{O}(n)，需要儲存事件、邊界座標與目前有效建築的堆。

Code

方法一：座標枚舉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def solve():
    buildings = []
    while True:
        try:
            l, h, r = map(int, input().split())
            buildings.append((l, h, r))
        except EOFError:  # 輸入結束
            break
        except ValueError:  # 輸入不足 3 個數
            break

    W = max(r for _, _, r in buildings)

    skyline = [0] * (W + 1)
    for l, h, r in buildings:
        for i in range(l, r):
            skyline[i] = max(skyline[i], h)

    ans = []
    prev_h = 0
    for i, h in enumerate(skyline):
        if h != prev_h:
            ans.append(f"{i} {h}")
            prev_h = h
    print(*ans)


if __name__ == "__main__":
    solve()

方法二：掃描線 + 最大堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from heapq import heappush, heappop
from collections import defaultdict


def solve():
    buildings = []
    while True:
        try:
            l, h, r = map(int, input().split())
            buildings.append((l, h, r))
        except EOFError:  # 輸入結束
            break
        except ValueError:  # 輸入不足 3 個數
            break

    Xs = set()
    events = defaultdict(list)
    for l, h, r in buildings:
        events[l].append((h, r))
        Xs.add(l)
        Xs.add(r)

    ans = []
    prev_h = 0
    hp = []
    for l in sorted(Xs):
        for h, r in events[l]:
            heappush(hp, (-h, r))

        while hp and hp[0][1] <= l:
            heappop(hp)

        h = -hp[0][0] if hp else 0
        if h != prev_h:
            ans.append(f"{l} {h}")
            prev_h = h
    print(*ans)


if __name__ == "__main__":
    solve()