略譯

原題目連結

給你 n 個東西的大小，
求最長區間長度，使得區間內所有東西的大小兩兩不相等

題解

按照題意模擬：

對任意區間，判斷區間內所有東西是否兩兩不相等

任意區間 n^2，直接暴力判斷 n^2，共 n^4
這題測資大，八成是 TLE

優化區間判斷

若我們在掃過每一個元素時，記錄它是否有出現過，
直接完美 hash 的話 n 次的 O(1) 查詢 => n，
使用 BST 或 map 的話 n 次的 log n 查詢 => n log n

一個能達成完美 hash 的方式是，
儘管輸入範圍到 signed int 的大小，卻能保證至多只有 n 個
並且原本的值不重要，只需要知道彼此相同不相同

在 sort 後，將相同物並排，即可把範圍為 signed int 的值，
轉存成此值為排行第 i 大；一樣大的就取相同的 i，就能將範圍壓縮至 <= n，又能判斷相不相等
便可在 n 大小的 table 上直接 hash
需要 n log n 的預處理，但具有相當小的常數

優化任意區間

很多區間根本不需要列入考慮，比如說：

當 [i, j] 並非兩兩不相等時，所有包含 [i, j] 的邊界全部都不符合條件
當 [i, j] 兩兩不相等時，所有被 [i, j] 包含的區間全部比 [i, j] 差

由第二點，得出固定右邊界時，只需考慮最佳的左邊界；
同理固定左邊界時，只需考慮最佳的右邊界。

得出一個做法：

• 枚舉 j 作為新的右邊界
• 對每個新邊界 j，自右邊界 j-1 時的左邊界 i 開始，刪除至不與新邊界 j 衝突

在枚舉中，考慮了所有可能的右邊界並固定、保證了左邊界必定最佳，
故枚舉的區間沒有遺漏

舉個例：12313

• j=0 => 12313 => [0, 0]
• j=1 => 12313 => [0, 1]
• j=2 => 12313 => [0, 2]
• j=3 => 12313 => 12313 => [1, 3]
• j=4 => 12313 => 12313 => 12313 => [3, 4]

每個元素只被加入一次、刪除一次，均攤後複雜度為線性，
即可枚舉出所有可能是解的區間。

綜合上述優化

在 n log n 預處理之後，線性掃過即可。

複雜度壓至 n log n。

經過相對繁雜的預處理，使用 qsort 與自刻 hash 執行時間 0.190
邊讀入邊以 map 直接運算，則只壓到了 0.280

實作提示

• 無