题解

题面描述

有一个经验池，需要支持三种操作，共有 $N$ 次操作：

1. 插入经验
   格式：+ id score
   向池中插入一个编号为 $id$ 的经验，初始优先级为 $score$。

题目内容

$AI$算力资源宝贵，在$AI$算法训练中，经验回放机制是通过存储和重用过去的经验数据来提高算法训练效率，以节省$AI$算力资源和提升算法训练迭代速度。为了进一步优化算法，我们使用优先级经验回放，根据每个经验的$TD$误差$(Temporal Difference Error)$动态调整其采样优先级。你需要设计一个高效的数据结构和算法来支持以下操作:

插入经验:将新经验加入经验池子，并赋予初始优先级。

提取$TopK$经验:取出优先级最高的$K$个经验用于算法训练。提取经验操作后，经验池子中就少了已经提取出去的经验。若经验池中剩余的经验个数小于$K$，则返回$-1$。

更新优先级:根据训练后的$TD$误差，更新指定经验的优先级。每次更新优先级操作后，之前提取出来的经验又都回到经验池子中，即经验池子包含了所有插入过的经验，且优先级为最新更新后的优先级。

给定$N$个按时间顺序发生的操作(插入/提取/更新)，请输出每次提取操作的结果。

输入描述

第一行为整数$N$，表示操作总数。

接下来$N$行，每行表示一个操作:

$insert\ id\ score$:插入$ID$为$id$的经验，初始优先级为$score$。$insert$操作用$+$表示。

$update\ id\ newScore$:将$ID$为$id$的经验优先级更新为$newScore$。$update$操作用=表示。

$extract\ k$:提取当前优先级最高的$k$个经验$id$(按经验的优先级降序排列，若优先级相同则按$id$升序排列)。$extract$操作用$-$表示。

约束条件: $1≤N≤10^5$

$1≤id≤10^5$(保证同一$id$不会被重复插入)

$0 < score,newScore≤10^9$

$1≤K≤10001$

输出描述

对每个$extract$操作，按顺序输出提取的$id$列表，用空格分隔。若有多次$extract$操作的输出，则后面的$extract$操作在前一次输出结果之后换行输出。注意:若$extract$操作的返回为$-1$，则输出$-1$。

若所有操作记录中没有$extract$操作，则返回$null$。

若入参的操作总数$N$和实际的操作行数不匹配，则返回$null$

样例1

输入

7
+ 1 5
+ 2 10
+ 3 7
- 2
= 3 20
- 1
- 1

输出

2 3
3
2

说明

初始经验池:$[(1,5),(2,10),(3,7)]$ 提取$Top2:2(10)→3(7)→$输出$2\ 3$

更新后经验池:$[(1,5),(2,10), (3,20)]$ 提取$Top1:3(20)→$输出$3$

经验池中剩余:$[(1,5),(2,10)]$ 提取$Top1:2(10)→$输出$2$

样例2

输入

3
+ 1 5
+ 2 10
- 4

输出

-1

说明

插入了$2$个经验值，最后要提取$4$个经验值;池子中的经验值不够数量，故返回$-1$