1912-设计电影租借系统

你有一个电影租借公司和 n 个电影商店。你想要实现一个电影租借系统，它支持查询、预订和返还电影的操作。同时系统还能生成一份当前被借出电影的报告。

所有电影用二维整数数组 entries 表示，其中 entries[i] = [shopi, moviei, pricei] 表示商店
shopi 有一份电影 moviei 的拷贝，租借价格为 pricei 。每个商店有 至多一份 编号为 moviei 的电影拷贝。

系统需要支持以下操作：

Search： 找到拥有指定电影且 未借出 的商店中 最便宜的 5 个 。商店需要按照价格升序排序，如果价格相同，则 shopi 较小的商店排在前面。如果查询结果少于 5 个商店，则将它们全部返回。如果查询结果没有任何商店，则返回空列表。
Rent： 从指定商店借出指定电影，题目保证指定电影在指定商店 未借出 。
Drop： 在指定商店返还 之前已借出 的指定电影。
Report： 返回 最便宜的 5 部已借出电影 （可能有重复的电影 ID），将结果用二维列表 res 返回，其中 res[j] = [shopj, moviej] 表示第 j 便宜的已借出电影是从商店 shopj 借出的电影 moviej 。res 中的电影需要按价格升序排序；如果价格相同，则 ****shopj 较小的排在前面；如果仍然相同，则 moviej 较小的排在前面。如果当前借出的电影小于 5 部，则将它们全部返回。如果当前没有借出电影，则返回一个空的列表。

请你实现 MovieRentingSystem 类：

MovieRentingSystem(int n, int[][] entries) 将 MovieRentingSystem 对象用 n 个商店和 entries 表示的电影列表初始化。
List<Integer> search(int movie) 如上所述，返回 未借出 指定 movie 的商店列表。
void rent(int shop, int movie) 从指定商店 shop 借出指定电影 movie 。
void drop(int shop, int movie) 在指定商店 shop 返还之前借出的电影 movie 。
List<List<Integer>> report() 如上所述，返回最便宜的 已借出 电影列表。

注意： 测试数据保证 rent 操作中指定商店拥有 未借出 的指定电影，且 drop 操作指定的商店 之前已借出 指定电影。

示例 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] ，商店 1，0 和 2 有未借出的 ID 为 1 的电影。商店 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] 。商店 0 和 1 有未借出的 ID 为 2 的电影。商店 0 最便宜，然后是商店 1 。

提示：

1 <= n <= 3 * 105
1 <= entries.length <= 105
0 <= shopi < n
1 <= moviei, pricei <= 104
每个商店至多有一份电影 moviei 的拷贝。
search，rent，drop 和 report 的调用总共不超过 105 次。

方法一：使用合适的数据结构

提示 1

对于一部电影，每个商店至多有它的拷贝，因此我们可以将 (\textit{shop}, \textit{movie}) 这一二元组作为数组 entries 中电影的唯一标识。

因此，我们可以使用一个哈希映射 t_price 存储所有的电影。对于哈希映射中的每一个键值对，键表示 (\textit{shop}, \textit{movie})，值表示该电影的价格。

提示 2

我们可以考虑禁止修改 t_price，即在任何情况下（例如 rent 操作或者 drop 操作），我们都不会去修改 t_price 本身。因此，我们需要两个额外的数据结构，一个存储未借出的电影 t_valid，一个存储已借出的电影 t_rent。

我们应该使用何种数据结构呢？

提示 3

对于未借出的电影，我们需要支持以下的三种操作：

search(movie) 操作，即给定 movie 查找出最便宜的 5 个 shop。因此，t_valid 最好「相对于 movie」是一个有序的数据结构。

我们可以考虑将 t_valid 设计成一个哈希映射，键表示 movie，值为一个有序集合（例如平衡树），存储了所有拥有 movie 的 shop。由于在 search 操作中，我们需要按照 price 为第一关键字，shop 为第二关键字返回结果，因此我们可以在有序集合中存储 (\textit{price}, \textit{shop}) 这一二元组。
rent(shop, movie) 操作。我们只需要通过 t_price}[(\textit{shop}, \textit{movie})] 得到 price，从 t_valid}[\textit{movie}] 中删除 (\textit{price}, \textit{shop}) 即可。
drop(shop, movie) 操作。我们只需要通过 t_price}[(\textit{shop}, \textit{movie})] 得到 price，将 (\textit{price}, \textit{shop}) 加入 t_valid}[\textit{movie}] 即可。

对于已借出的电影，我们需要支持以下的三种操作：

report() 操作，即查找出最便宜的 5 部电影。由于我们需要按照 price 为第一关键字，shop 为第二关键字，movie 为第三关键字返回结果，因此我们同样可以使用一个有序集合表示 t_rent，存储三元组 (\textit{price}, \textit{shop}, \textit{movie})。
rent(shop, movie) 操作。我们只需要通过 t_price}[(\textit{shop}, \textit{movie})] 得到 price，将 (\textit{price}, \textit{shop}, \textit{movie}) 加入 t_rent 即可。
drop(shop, movie) 操作。我们只需要通过 t_price}[(\textit{shop}, \textit{movie})] 得到 price，从 t_rent 中删除 (\textit{price}, \textit{shop}, \textit{movie}) 即可。

思路与算法

我们使用提示部分提及的数据结构 t_price，t_valid，t_rent。

对于 MovieRentingSystem(n, entries) 操作：我们遍历 entries 中的 (\textit{shop}, \textit{movie}, \textit{price})，将 (\textit{shop}, \textit{movie}) 作为键、price 作为值加入 t_price，并且将 (\textit{price}, \textit{shop}) 加入 t_valid}[\textit{movie}]。
对于 search(movie) 操作，我们遍历 t_valid}[\textit{movie}] 中不超过 5 个 (\textit{price}, \textit{shop})，并返回其中的 shop。
对于 rent(shop, movie) 操作，我们通过 t_price}[(\textit{shop}, \textit{movie})] 得到 price，从 t_valid}[\textit{movie}] 中删除 (\textit{price}, \textit{shop})，并且将 (\textit{price}, \textit{shop}, \textit{movie}) 加入 t_rent。
对于 drop(shop, movie) 操作，我们通过 t_price}[(\textit{shop}, \textit{movie})] 得到 price，将 (\textit{price}, \textit{shop}) 加入 t_valid}[\textit{movie}]，并且从 t_rent 中删除 (\textit{price}, \textit{shop}, \textit{movie})。
对于 report() 操作，我们遍历 t_rent 中不超过 5 个 (\textit{price}, \textit{shop}, \textit{movie})，并返回其中的 (\textit{shop}, \textit{movie})。

代码

[sol1-C++]class MovieRentingSystem {
private:
    # 需要自行实现 pair<int, int> 的哈希函数
    static constexpr auto pairHash = [fn = hash<int>()](const pair<int, int>& o) {return (fn(o.first) << 16) ^ fn(o.second);};
    unordered_map<pair<int, int>, int, decltype(pairHash)> t_price{0, pairHash};

    unordered_map<int, set<pair<int, int>>> t_valid;

    set<tuple<int, int, int>> t_rent;

public:
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for (const auto& entry: entries) {
            t_price[{entry[0], entry[1]}] = entry[2];
            t_valid[entry[1]].emplace(entry[2], entry[0]);
        }
    }
    
    vector<int> search(int movie) {
        if (!t_valid.count(movie)) {
            return {};
        }
        
        vector<int> ret;
        auto it = t_valid[movie].begin();
        for (int i = 0; i < 5 && it != t_valid[movie].end(); ++i, ++it) {
            ret.push_back(it->second);
        }
        return ret;
    }
    
    void rent(int shop, int movie) {
        int price = t_price[{shop, movie}];
        t_valid[movie].erase({price, shop});
        t_rent.emplace(price, shop, movie);
    }
    
    void drop(int shop, int movie) {
        int price = t_price[{shop, movie}];
        t_valid[movie].emplace(price, shop);
        t_rent.erase({price, shop, movie});
    }
    
    vector<vector<int>> report() {
        vector<vector<int>> ret;
        auto it = t_rent.begin();
        for (int i = 0; i < 5 && it != t_rent.end(); ++i, ++it) {
            ret.emplace_back(initializer_list<int>{get<1>(*it), get<2>(*it)});
        }
        return ret;
    }
};

[sol1-Python3]class MovieRentingSystem:

    def __init__(self, n: int, entries: List[List[int]]):
        self.t_price = dict()
        self.t_valid = defaultdict(sortedcontainers.SortedList)
        self.t_rent = sortedcontainers.SortedList()
        
        for shop, movie, price in entries:
            self.t_price[(shop, movie)] = price
            self.t_valid[movie].add((price, shop))

    def search(self, movie: int) -> List[int]:
        t_valid_ = self.t_valid
        
        if movie not in t_valid_:
            return []
        
        return [shop for (price, shop) in t_valid_[movie][:5]]
        
    def rent(self, shop: int, movie: int) -> None:
        price = self.t_price[(shop, movie)]
        self.t_valid[movie].discard((price, shop))
        self.t_rent.add((price, shop, movie))

    def drop(self, shop: int, movie: int) -> None:
        price = self.t_price[(shop, movie)]
        self.t_valid[movie].add((price, shop))
        self.t_rent.discard((price, shop, movie))

    def report(self) -> List[List[int]]:
        return [(shop, movie) for price, shop, movie in self.t_rent[:5]]

复杂度分析

时间复杂度：
- MovieRentingSystem(n, entries) 操作：O(n \log n)。
- search(movie) 操作：O(\log n)。
- rent(shop, movie) 操作：O(\log n)。
- drop(shop, movie) 操作：O(\log n)。
- report() 操作：O(\log n)。
空间复杂度：O(n)。