HDU 4343 Interval Query：倍增 + 貪心 + 離散化求區間最大不相交子集

題目大意

給定 n, m ≤ 10⁵ 個區間（左閉右開）與詢問 [L, R]。每次詢問：僅考慮完全包含在 [L, R] 內的區間，求其最大不相交子集大小。

關鍵觀察：貪心 + 區間包含關係去除

• 若區間 A 包含區間 B，選 A 永不優於選 B（B 結束更早，留給後續更多空間）。故可預處理刪除所有「被其他區間包含」的區間。
• 剩餘區間按左端點遞增排序，右端點也必遞增（否則會有包含關係）。
• 對固定 [L, R]，最優策略：從 L 起，反覆選擇「左端點 ≥ 當前位置且右端點最小」的區間，更新當前位置為該區間右端點。即標準「區間調度」貪心。

倍增加速：f[i][j] 表示從離散點 i 起跳 2ʲ 個區間到達的最遠位置

• 離散化所有區間端點與詢問端點，得到有序座標 xs[]。
• 預處理 nxt[i] = 從 xs[i] 出發，選擇左端點 ≥ xs[i] 的第一個區間的右端點（離散索引）。若無則 INF。
• 倍增表：f[i][0] = nxt[i]，f[i][j] = f[ f[i][j-1] ][j-1]（j ≤ 16 因 2¹⁶ > 10⁵）。

詢問回答：二分跳躍

對詢問 [L, R] 離散為 l, r：

ans = 0
for j = 16 down to 0:
    if f[l][j] <= r:
        l = f[l][j]
        ans += 1 << j
return ans

即在 O(log N) 內求出最大跳躍步數。

複雜度

• 離散化 O((n+m) log(n+m))。
• 預處理 O(N log N)（N = |xs| ≤ 4×10⁵）。
• 每查詢 O(log N)，總 O(m log N)。
• 記憶體 f[N][17] ≈ 6.8×10⁶ int ≈ 27 MB，安全。

實作細節

• 區間排序：l 升序，l 同則 r 降序，便於掃描構建 nxt[]。
• nxt[] 構建：從右向左掃描離散點，維護當前最優區間。
• 詢問離散化：L → lower_bound，R → upper_bound - 1（因區間右開）。

總結

本題將「區間最大不相交子集」轉化為「從左到右貪心跳躍」，利用倍增將單次查詢從 O(答案) 降為 O(log N)，配合離散化處理大座標範圍。是「貪心 + 倍增 + 離散化」三大技巧結合的經典範例。