2424. Longest Uploaded Prefix

Longest Uploaded Prefix

題目描述： 設計一個系統來追蹤影片上傳進度。影片編號從 1 到 n，可以按任意順序上傳。upload(video) 上傳指定編號的影片。longest() 返回最長的已上傳前綴長度，即找到最大的 i 使得 1, 2, ..., i 都已上傳。

解題思路： 使用一個集合記錄已上傳的影片，並維護一個指標 prefix 表示當前最長前綴。每次上傳後，檢查是否可以延伸前綴：如果上傳的影片編號恰好是 prefix + 1 或之後的連續編號，就持續推進 prefix。

具體做法：維護 prefix 初始為 0。每次 upload(video) 後，若 video 被標記已上傳，則嘗試推進 prefix（while prefix+1 已上傳 → prefix++）。

時間複雜度：upload 攤銷 O(1)（prefix 最多從 0 推進到 n，總共 O(n) 次推進分攤到 n 次 upload 呼叫）；longest 為 O(1)

空間複雜度：O(n) — 集合儲存已上傳的影片

1. 布林陣列法：用 vector<bool> uploaded(n+1) 代替 hash set。查詢 O(1) 且記憶體更緊湊（每個元素 1 bit），但需要預先知道 n 的大小。

2. Union-Find 法：每次上傳時將 video 與 video-1（若已上傳）合併。longest() 返回包含 1 的連通分量大小。時間複雜度 O(α(n))，但實作較複雜且不如前兩種方法直觀。

1. 如果影片可以被「刪除」（取消上傳），prefix 需要如何維護？
2. 如果要支援查詢「從影片 k 開始的最長連續已上傳段」，資料結構如何設計？
3. 如果影片編號不是連續的 1~n 而是任意正整數，如何調整？