题面

让我们来为某场 ICPC 比赛写一个排名系统吧！

ICPC 的规则就不再细讲了吧（逃

算了还是简单讲讲吧，首先排名按照 AC 题目顺序由大到小排。如果两队 AC 题目数量相同，则罚时较小的队伍在前。若两队 AC 题目和罚时大小都相同，则两队排名相同。一次未通过的提交会使得该队该题上的罚时额外加 $20$ 分钟，但只有在该题 AC 后才会被计入总罚时。若该队在某题上第一次提交就 AC 了，则罚时为 AC 时的时间。

这场比赛有 $N$ 支队伍参加，且包含 $M$ 道题目。

排名系统会收到三种指令：

1. 提交

格式： S [提交时间]:[队伍 ID]:[题目 ID]:[评测结果]

如果一个队伍重复提交某道他们之前已经 AC 过的题目，或是本次提交据上次有效提交少于 $5$ 分钟，则此次提交会被认定为无效并被系统忽略。否则，系统认定本次提交有效。

2. 依据队伍 ID 查询排名

格式：R [队伍ID]

需要注意的是，如前面所讲，可能出现若干队排名相同的情况。

3. 依据排名查询队伍 ID

格式：T [排名]

如果该排名下由多支队伍，则输出上次 AC 时间最早的队伍。如果所有队伍都没有 AC 题目，则输出 ID 最小的队伍。如果该排名不存在，则输出 $-1$ 。

数据范围：

比赛时长不会超过 $5$ 小时（$300$ 分钟）

$1 \le N \le 10^4$

$1 \le M \le 10$

每次比赛的指令次数不超过 $10^5$ 次。

题目链接

分析

这种查询排名的题目一看就会勾引我们往平衡树想…… 正巧前天瞎学了学无旋转的 Treap，于是我们就来试试能不能水过这道题吧……

我们可以首先把一个队伍的 AC 题目数量和罚时打包成一个代表分数的结构体，并将其小于和等于符号重载掉。

那么 Treap 上维护什么呢…… 如果我们把每个队伍都当作一个节点放到 Treap 上维护的话，更新队伍的分数是很难做到的。毕竟本蒟蒻只会不带旋转的 Treap，如果要改变某节点的值必须要先将原节点删除然后再插入新节点，这样的话光删除操作就很难实现，所以…… 看起来行不通。

不过我们可以换个思路，考虑一个分数一个节点，然后在每个节点上再套一个 $set$ 来记录该分数下有哪些队伍。这样就要方便不少。不过这样一来，以某节点为根的子树大小就不再是 $\text{leftSon} + \text{rightSon} + 1$ 了，而应该是 $\text{leftSon} + \text{rightSon} + set.\text{size()}$ 。同时，插入和删除时就变成了先通过 split 操作分离出代表需更新队伍的分数的节点（如果该节点不存在的话就需要新建一个），然后对该节点上的 $set$ 进行 $\text{insert}$ 或者 $\text{erase}$ 操作，最后再把它们 merge 回去。$set$ 内可以根据第三类操作的输出顺序排序，这样在执行第三类操作时直接返回第一个元素就好了。至于很多其它细节，看看参考代码大概就会了。

怎么题面比口胡题解还长啊…… 羞愧 🙈

实现

完整参考代码