2276. Count Integers in Intervals

Count Integers in Intervals

題目描述： 設計一個資料結構，支援兩個操作：add(left, right) 將區間 [left, right] 加入集合，count() 回傳集合中包含的不同整數數量（重疊的只算一次）。

解題思路： 使用有序映射（C++ 的 map）維護互不重疊的區間集合。

1. 用 map<int, int> 存儲區間，key = left，value = right。保持所有區間互不重疊。
2. add(left, right)：
   • 找到所有與 [left, right] 重疊的現有區間。
   • 合併它們：新的 left 取所有重疊區間左端的最小值，新的 right 取所有重疊區間右端的最大值。
   • 刪除所有被合併的舊區間，插入新的合併區間。
   • 更新計數：加上新增的整數數量。
3. count()：直接回傳維護的計數值。

使用 map 的 lower_bound 可以高效找到需要合併的區間。

時間複雜度：add 均攤 O(log n)，count O(1) — 每個區間最多被合併（刪除）一次，add 的總代價均攤為 O(n log n)（n 次操作）。

空間複雜度：O(n) — 最多存儲 n 個互不重疊的區間。

1. 線段樹（動態開點）：使用動態開點的線段樹，add 操作標記區間，count 查詢根節點的覆蓋數。支援更靈活的查詢（如查詢子區間），但實作複雜，空間 O(n log V)，V 為值域。

2. 座標壓縮 + BIT：將所有出現的端點離散化，用樹狀陣列維護覆蓋狀態。需要離線處理（預先知道所有操作），不適合在線（online）場景。

1. 若需要支援刪除操作 remove(left, right)（從集合中移除區間），合併映射如何處理分裂的情況？
2. 若值域非常大（如 10^18），map 方法仍然可行嗎？線段樹需要如何適配？
3. 若要支援查詢「第 K 個被覆蓋的整數是什麼」，資料結構需要什麼擴展？