解題說明
Count Integers in Intervals
題目描述： 設計一個資料結構，支援兩個操作：add(left, right) 將區間 [left, right] 加入集合，count() 回傳集合中包含的不同整數數量（重疊的只算一次）。
解題思路：
使用有序映射（C++ 的 map）維護互不重疊的區間集合。
- 用
map<int, int>存儲區間，key = left，value = right。保持所有區間互不重疊。 - add(left, right)：
- 找到所有與 [left, right] 重疊的現有區間。
- 合併它們：新的 left 取所有重疊區間左端的最小值，新的 right 取所有重疊區間右端的最大值。
- 刪除所有被合併的舊區間，插入新的合併區間。
- 更新計數：加上新增的整數數量。
- count()：直接回傳維護的計數值。
使用 map 的 lower_bound 可以高效找到需要合併的區間。
C++ 解法
複雜度分析
時間複雜度：add 均攤 O(log n)，count O(1) — 每個區間最多被合併（刪除）一次，add 的總代價均攤為 O(n log n)（n 次操作）。
空間複雜度：O(n) — 最多存儲 n 個互不重疊的區間。
虛擬碼
1. Maintain a sorted map of non-overlapping intervals [left, right] and a total count. 2. ADD(left, right): a. Find all existing intervals that overlap with [left-1, right+1] (touching counts as overlap for merging). b. newLeft = min(left, all overlapping lefts). c. newRight = max(right, all overlapping rights). d. Subtract old interval sizes from count, delete them. e. Insert [newLeft, newRight], add its size to count. 3. COUNT(): return cnt.
其他解法
-
線段樹（動態開點）：使用動態開點的線段樹，add 操作標記區間，count 查詢根節點的覆蓋數。支援更靈活的查詢（如查詢子區間），但實作複雜，空間 O(n log V)，V 為值域。
-
座標壓縮 + BIT：將所有出現的端點離散化，用樹狀陣列維護覆蓋狀態。需要離線處理（預先知道所有操作），不適合在線（online）場景。
延伸思考
- 若需要支援刪除操作 remove(left, right)（從集合中移除區間），合併映射如何處理分裂的情況？
- 若值域非常大（如 10^18），map 方法仍然可行嗎？線段樹需要如何適配？
- 若要支援查詢「第 K 個被覆蓋的整數是什麼」，資料結構需要什麼擴展？