# 2102. 序列顺序查询
### 题目地址(2102. 序列顺序查询)
### 题目描述
```
一个观光景点由它的名字 name 和景点评分 score 组成，其中 name 是所有观光景点中 唯一 的字符串，score 是一个整数。景点按照最好到最坏排序。景点评分 越高 ，这个景点越好。如果有两个景点的评分一样，那么 字典序较小 的景点更好。
你需要搭建一个系统，查询景点的排名。初始时系统里没有任何景点。这个系统支持：
添加 景点，每次添加 一个 景点。
查询 已经添加景点中第 i 好 的景点，其中 i 是系统目前位置查询的次数（包括当前这一次）。
比方说，如果系统正在进行第 4 次查询，那么需要返回所有已经添加景点中第 4 好的。
注意，测试数据保证 任意查询时刻 ，查询次数都 不超过 系统中景点的数目。
请你实现 SORTracker 类：
SORTracker() 初始化系统。
void add(string name, int score) 向系统中添加一个名为 name 评分为 score 的景点。
string get() 查询第 i 好的景点，其中 i 是目前系统查询的次数（包括当前这次查询）。
示例：
输入：
["SORTracker", "add", "add", "get", "add", "get", "add", "get", "add", "get", "add", "get", "get"]
[[], ["bradford", 2], ["branford", 3], [], ["alps", 2], [], ["orland", 2], [], ["orlando", 3], [], ["alpine", 2], [], []]
输出：
[null, null, null, "branford", null, "alps", null, "bradford", null, "bradford", null, "bradford", "orland"]
解释：
SORTracker tracker = new SORTracker(); // 初始化系统
tracker.add("bradford", 2); // 添加 name="bradford" 且 score=2 的景点。
tracker.add("branford", 3); // 添加 name="branford" 且 score=3 的景点。
tracker.get(); // 从好带坏的景点为：branford ，bradford 。
// 注意到 branford 比 bradford 好，因为它的 评分更高 (3 > 2) 。
// 这是第 1 次调用 get() ，所以返回最好的景点："branford" 。
tracker.add("alps", 2); // 添加 name="alps" 且 score=2 的景点。
tracker.get(); // 从好到坏的景点为：branford, alps, bradford 。
// 注意 alps 比 bradford 好，虽然它们评分相同，都为 2 。
// 这是因为 "alps" 字典序 比 "bradford" 小。
// 返回第 2 好的地点 "alps" ，因为当前为第 2 次调用 get() 。
tracker.add("orland", 2); // 添加 name="orland" 且 score=2 的景点。
tracker.get(); // 从好到坏的景点为：branford, alps, bradford, orland 。
// 返回 "bradford" ，因为当前为第 3 次调用 get() 。
tracker.add("orlando", 3); // 添加 name="orlando" 且 score=3 的景点。
tracker.get(); // 从好到坏的景点为：branford, orlando, alps, bradford, orland 。
// 返回 "bradford".
tracker.add("alpine", 2); // 添加 name="alpine" 且 score=2 的景点。
tracker.get(); // 从好到坏的景点为：branford, orlando, alpine, alps, bradford, orland 。
// 返回 "bradford" 。
tracker.get(); // 从好到坏的景点为：branford, orlando, alpine, alps, bradford, orland 。
// 返回 "orland" 。
提示：
name 只包含小写英文字母，且每个景点名字互不相同。
1 <= name.length <= 10
1 <= score <= 105
任意时刻，调用 get 的次数都不超过调用 add 的次数。
总共 调用 add 和 get 不超过 4 * 104
```
### 前置知识
* 平衡二叉树
### 公司
* 暂无
### 思路
这种题目适合使用平衡二叉树来做。如果对其不熟悉，可以参考我的二分专题。
另外这种动态求极值的，也可以考虑使用堆。不过我们求的是 第 k 大，而不是最大。因此可使用堆中的固定堆技巧来实现。具体可以参考我的堆专题。
想到使用平衡二叉树后，思路就简单了。 一开始我的想法是：
```py
from sortedcontainers import SortedList
class SORTracker:
def __init__(self):
sl = SortedList()
self.i = -1
self.sl = sl
def add(self, name: str, score: int) -> None:
self.sl.add((score, name))
def get(self) -> str:
ans = self.sl[self.i][1]
self.i += 1
return ans
```
不过这是不对的。
这是因为题目约定了**如果有两个景点的评分一样，那么 字典序较小 的景点更好**。
而上面的代码会返回字典序较大的。一种简单的想法是 add 的时候将 name 取反放进去。由于字符串不能直接取反，我们需要先想办法把他们转为数字进行处理。代码如下
```py
from sortedcontainers import SortedList
class SORTracker:
def __init__(self):
sl = SortedList()
self.i = -1
self.sl = sl
def add(self, name: str, score: int) -> None:
self.sl.add((score, -1 * toNumber(name) ,name))
def get(self) -> str:
ans = self.sl[self.i][2]
self.i += 1
return ans
```
实际上一种更简单的方法是 add 的时候对 score 进行取反，接下来 get 的时候从另外一头取即可。 具体见下方代码。
### 关键点
* add 的时候对 score 取反，达到**如果有两个景点的评分一样，那么 字典序较小 的景点更好**的效果。
### 代码
* 语言支持：Python3
Python3 Code:
```python
from sortedcontainers import SortedList
class SORTracker:
def __init__(self):
sl = SortedList()
self.i = 0
self.sl = sl
def add(self, name: str, score: int) -> None:
self.sl.add((-score, name))
def get(self) -> str:
ans = self.sl[self.i][1]
self.i += 1
return ans
# Your SORTracker object will be instantiated and called as such:
# obj = SORTracker()
# obj.add(name,score)
# param_2 = obj.get()
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(logn)$
* 空间复杂度：$O(n)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
