題目連結：
題目大意：
第一列給定兩正整數 n 、 L （1 ≦ n ≦ 200000，1 ≦ L ≦ 10 ^ 7），代表要對一根長度為 L 單位的根子切 n 刀（每刀的位置保證不一樣）。棍子從左到右編訂位置 0 ～ L 。
接著有 n 列輸入，每列給定兩正整數 x 、 i （0 < x < L，1 ≦ i ≦ n），代表第 i 刀下刀的位置為 x 。每一次下刀的成本為被切的棍子段（可能已經切很多刀使得原本的棍子分成好幾段）之長度。
試問總成本為多少？
範例輸入：
3 7
2 2
3 1
5 3
範例輸出：
14
解題思維：
先將每一刀的正確順序重組回去（因為給定的順序不一定照下刀的順序）。
接著掃過每一刀下刀的位置，對於每個位置去找其處於的棍子段之開頭位置以及結尾位置。但是每次遍歷先前所有棍子的開頭、結尾位置並不是很理想（太慢）。
而我們可以使用平衡二元搜尋樹（Self-Balancing Binary Search Tree，如此有 AVL 樹或是紅黑樹等資料結構，例如 C++ 的 set 以及 map 即以紅黑樹實作）去儲存每個棍子段的開頭位置（一開始只有 0 ～ L 的原棍子，所以只有存 0）。
如此一來每一次搜尋的時間複雜度從全數掃過的 O(n) 變為 O(log n)，所以掃過所有下刀位置並計算成本的時間複雜度為 O(n log n)。而每一刀的成本總和即是所求。
此外，以下是 C++ 使用 set 去儲存棍子開頭位置時應注意的事：
宣告一集合為 set <int> segments; 後，每次搜尋不應使用
lower_bound(segments.begin(), segments.end(), x);
去尋找位置 x （upper_bound 也同理，不應使用），應當使用
segments.lower_bound(x);
因為 C++ 的 set 資料結構不支援隨機存取（Random Access）。而 <algorithm> 標頭檔定義的 lower_bound() 需要資料結構能被隨機存取（當然，其中資料還需為已排序）才能最佳化為每次搜尋為 O(log n)；否則，其將為線性搜尋，即 O(n)。
而 set::lower_bound() 則是利用本身資料結構的特性——其本質是一棵二元搜尋樹（Binary Search Tree），所以搜尋只需 O(log n)。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
