主題
題目連結：
題目意譯：
你有著電影租借企業由 n 個店鋪組成。你想要實作一個租借系統，其支援搜尋、借閱和返還電影。系統也應要可以支援生成一份目前被借閱之電影的報告。
每部電影給定於一個 2D 整數至列 entries，其中 entries[i] = [shopi, moviei, pricei] 代表著店鋪 shopi 有著一份電影 moviei 之副本而租借費用為 pricei。每間店鋪最多只會擁有一部電影 moviei 之副本。
系統應支援以下函式：
Search：找到最便宜的 5 間店鋪，其有著給定之電影的未租借副本。店鋪應按照價格升序排列，而如果平手，則較小的 shopi 之值應排於前。如果只有不到 5 間店鋪符合，則它們全數應被回傳。如果沒有店鋪有著未被租借之副本，則回傳一空列表。
Rent：從給定的店鋪租借給定的電影之未租借副本。
Drop：將給定的先前租借之電影退回到給定的店鋪。
Report：回傳最便宜的 5 部已租借之電影（有可能有著同樣的電影ID）為一個 2D 列表 res，其中 res[j] = [shopj, moviej] 代表著第 j 便宜的已租借電影 moviej 是從 shopj 借來的。電影應按價格升序排列，如果平手，則將較小 shopj 之值排於前，而如果又平手，則將較小 moviej 之值排於前。如果少於 5 部已租借電影，則應全數回傳。如果現在沒有電影被租借，則回傳一個空列表。
實作類別 MovieRentingSystem：
MovieRentingSystem(int n, int[][] entries) 初始化 MovieRentingSystem 物件，其有著 n 間店鋪以及 entries 裡面的電影。
List<Integer> search(int movie) 回傳一個店鋪列表，其有著如上所述給定電影之未租借副本。
void rent(int shop, int movie) 從給定的店鋪租借給定的電影之未租借副本。
void drop(int shop, int movie) 將給定的先前租借之電影退回到給定的店鋪。
List<List<Integer>> report() 回傳最便宜的已租借電影之列表如上所述。
注：測資之產生保證 rent 只會呼叫於 shop 有著一份未被租借之 movie 副本，而 drop 則將只會呼叫於 shop 在先前有出租 movie 的時候。
限制：
1 ≦ n ≦ 3 × 10 ^ 5
1 ≦ entries.length ≦ 10 ^ 5
0 ≦ shopi < n
1 ≦ moviei 、 pricei ≦ 10 ^ 4
每間店鋪最多只會擁有一部電影 moviei 之副本。
最多 10 ^ 5 次呼叫為 search 、 rent 、 drop 和 report。
範例測資：
範例 1：
輸入
["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]
[[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]]
輸出
[null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]
解釋
MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);
movieRentingSystem.search(1); // 回傳 [1, 0, 2]，電影 ID 為 1 有著未租借副本於店鋪 1 、 0 和 2。店鋪 1 是最便宜的；店鋪 0 和 2 則為相同價格，所以按照店鋪編號排序。
movieRentingSystem.rent(0, 1); // 從店鋪 0 租借電影 1。店鋪 0 中未被租借的電影為 [2,3]。
movieRentingSystem.rent(1, 2); // 從店鋪 1 租借電影 2。店鋪 1 中未被租借的電影為 [1]。
movieRentingSystem.report(); // 回傳 [[0, 1], [1, 2]]。店鋪 0 的電影 1 最便宜，其後跟著店鋪 1 的電影 2。
movieRentingSystem.drop(1, 2); // 從店鋪 1 歸還電影 2。店鋪 1 中未被租借的電影為 [1,2]。
movieRentingSystem.search(2); // 回傳 [0, 1]。電影 ID 為 2 有著未租借副本於店鋪 0 和 1。店鋪 0 最便宜，其後跟著店鋪 1。
解題思維：
因為我們暨要統計已租借的電影哪幾部最便宜（report），又要可以將插入新的租借電影和已租借的電影歸還回去。因此每種操作如果都是 O(log M) 是最好的，其中 M 為電影的總數。
因此我們需要平衡二元搜尋樹（Balanced Binary Search Tree），例如 C++ 中的 set 、 map 之容器或是 Python 中的 SortedList。以下用 C++ 做例子：
我們定義兩個雜湊表（Hash Table）prices 、 movieUnrented，前者以 {shop, movie} 作為鍵值（租借時很方便，直接 prices[{shop, movie}] 便可以 O(1) 取得電影的價格）、後者以 movie 作為鍵值且映射值為一個 set ，其鍵值為 {price, shop}。而因為上面提及的平衡二元搜尋樹所以這個 set 的開頭將是以 price 最小的作為開始（所以用來搜尋最便宜的電影很方便）。
然後我們再定義一個 set ，其將 {price, shop, movie} 作為鍵值。根據 set 的特性，它會先按 price 排序、一樣再按 shop 排序、再來則是 movie。
因此我們一開始初始化的時候，對於 entries 裡面每個項目 entry，把 prices[{entry[0], entry[1]}] 這個鍵值的映射值設為 entry[2]，代表店鋪 entry[0] 有著電影 entry[1] 價格為 entry[2]。還要將 movieUnrented[entry[1]] 這個鍵值所對應的 set 放入 {entry[2], entry[0]}，代表要把電影 entry[1] 的未租借副本先按價格 entry[2] 排序再按商店 entry[0] 排。
所以當我們：
呼叫 search(movie) 時，我們只要到 movieUnrented[movie] 的 set 中把前 5 個（如果不到 5 個就是全部）元素抓出來，然後從中擷取出店鋪的編號即可。
呼叫 rent(shop, movie) 時，利用 prices[{shop, movie}] 便可以得到該電影於該店鋪的價格 P。此時我們將 rentedCost 放入這個被租借的電影之資訊 {P, shop, movie}（然後 set 這個結構就會自動地幫我們排序好）。然後我們將 movieUnrented[movie] 的映射之 set 從中抹除掉 {P, shop} 這個元素。因為該電影已經於該店鋪中被借走了。
呼叫 drop(shop, movie) 時，利用 prices[{shop, movie}] 便可以得到該電影於該店鋪的價格 P。然後做跟 rent() 相反的事——從 rentedCost 移除 {P, shop, movie} 、 將 movieUnrented[movie] 映射之 set 放入 {P, shop} 之元素。表示該電影於該店鋪又可以被租借了。
呼叫 report 時，我們只要掃過 rentedCost 去找出前 5 部（如果不夠 5 部，則為全部）電影即可得到最便宜的電影之店鋪編號和電影編號。
如上，每個操作都是 O(log M)。這樣便可以在時限之內完成每次的呼叫或詢問。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
