UVA 1455 Kingdom：並查集維護州連通+線段樹統計水平線穿越

UVA 1455 Kingdom：並查集維護州連通+線段樹統計水平線穿越

平面上 n 城市，初始無道路。操作：road A B 連接城市；line C 查詢 y=C 水平線穿過多少州及城市總數。州=連通分量。C 為 .5 結尾實數。

核心數據結構

• 並查集：維護城市連通分量，記錄每集合的 y 坐標範圍 [l, r] 及城市數 d。
• 線段樹：離散化 y 座標（整數坐標），每個葉子代表單位區間。節點維護 nc(城市數增量) 和 nz(州數增量)。

合併兩州時線段樹更新邏輯

設兩州 y 範圍分別為 [l1, r1], [l2, r2]（假設 l1 ≤ l2）。

• 若不相交（l2 ≥ r1）：中間間隙 [r1, l2] 新增 1 州（nz+=1），右州範圍 [r1, r2] 城市數增量 nc+=d1。
• 若包含（r2 ≤ r1）：右州內部 [l2, r2] 減少 1 州（nz-=1），左州外部 [r2, r1] 城市數增量 nc+=d2。
• 相交不包含：綜合上述區間更新。
• 最後左端點 [l1, l2] 城市數增量 nc+=d2（合併後新州範圍擴大）。

查詢處理

line C → 離散化索引查詢線段樹單點值，輸出 nz (州數) 和 nc (城市數)。

複雜度

• 並查集：近似 O(α(n))。
• 線段樹更新/查詢：O(log Y)，Y 為離散化坐標數（≤ 1e6）。
• 總體高效支持大規模操作。

本題巧妙結合並查集動態連通與線段樹區間加點查，將幾何統計問題轉化為數據結構維護，是綜合類難題佳作。