题目内容

某大数据监控系统需要实时跟踪海量日志中出现的热门关键词。系统设定了一个容量为 $W$ 的滑动窗口，仅统计最近进入窗口的一批关键词。每当一个新关键词到达时，它会被放入窗口尾部；如果窗口中的关键词数量超过了 $W$，则窗口头部最早进入的关键词会被移出，并且该关键词的频次需要相应减少；如果某关键词的频次降为 0，就认为当前窗口中不再存在该关键词。

请实现一个组件，支持以下两种操作：

• add(word)：将关键词 word 添加到滑动窗口。若窗口大小超过 $W$，按先进先出（$FIFO$）规则淘汰最早进入的关键词，并更新计数。
• get_top(k)：查询窗口内出现次数最高的前 $k$ 个关键词。返回结果按出现次数从大到小排序；出现次数相同时按字典序从小到大排序。若窗口内不同关键词的数量少于 $k$，则返回全部关键词。

约束条件：

• $W$ 和 $Q$ 均为整数，取值范围均为 1 到 100000。
• 每个添加的关键词 $x$ 是由小写英文字母组成的字符串，长度在 1 到 20 之间。
• 查询参数 $k$ 是整数，取值范围为 1 到 100000。
• 保证每次执行 get_top(k) 查询时，滑动窗口内至少有一个元素。
• 保证每个测试用例中至少包含一次 get_top(k) 查询。

输入描述

第一行包含两个整数 $W$ 和 $Q$，分别表示滑动窗口大小和操作总数。

接下来 $Q$ 行，每行描述一个操作，格式如下：

• add x：添加关键词 $x$。
• get k：查询当前窗口内出现次数最高的 $k$ 个关键词。

输出描述

对于每个 get k 操作，输出一行。结果包含按规则排列的若干个关键词；如果关键词数量多于 1 个，则相邻关键词之间用单个空格分隔，行末不能有多余空格。如果当前窗口内不同关键词数量少于 $k$，则输出这些关键词。

样例1

输入

4 8
add a
add b
add c
add a
get 2
add b
add d
get 3

输出

a b
a b c

说明

窗口大小 $W=4$。前 4 条 add 后，窗口内容为 a b c a，对应频次为 $a:2$、$b:1$、$c:1$。第一次 get 2 时，a 的频次最高，b 和 c 频次相同且 b 字典序更小，因此输出 a b。

随后 add b：新 b 进入尾部，窗口长度超过 4，淘汰队首的 a。此时频次变为 $a:1$、$b:2$、$c:1$。再 add d：淘汰队首的 b，加入 d，频次变为 $a:1$、$b:1$、$c:1$、$d:1$。

第二次 get 3 时，所有关键词频次均为 1，按字典序排列为 a b c d，取前 3 个，输出 a b c。

样例2

输入

1 6
add apple
add banana
add apple
get 1
add cherry
get 3

输出

apple
cherry

说明

窗口大小 $W=1$，窗口最多只能保留 1 个关键词。

前 3 次添加：add apple 后窗口为 apple；add banana 时长度超过 1，淘汰 apple，窗口只剩 banana；add apple 时淘汰 banana，窗口只剩 apple。

第一次 get 1 查询时，窗口内只有 apple，因此输出 apple。

接着 add cherry 会淘汰当前唯一的 apple，窗口变为 cherry。第二次 get 3 的查询参数 $k=3$，但窗口内不同关键词只有 1 个，因此返回全部，输出 cherry。

样例3

输入

3 6
add apple
add banana
add cherry
get 5
add apple
get 2

输出

apple banana cherry
apple banana

说明

窗口大小 $W=3$。

前 3 个 add 后，窗口为 apple banana cherry，频次均为 1。第一次 get 5 时，查询参数 $k=5$ 大于当前不同关键词数量 3，所以返回全部关键词。频次相同，按字典序排列为 apple banana cherry。

然后 add apple：新 apple 进入尾部，长度变为 4，淘汰队首的旧 apple。淘汰和新增相互抵消，窗口变为 banana cherry apple，三个关键词频次仍都是 1。

第二次 get 2 时，三个关键词频次相同，按字典序 apple 最小，其次是 banana，因此取前 2 个，输出 apple banana。

样例4

输入

2 6
add a
add a
get 1
add a
add a
get 1

输出

a
a

说明

窗口大小 $W=2$。

连续执行两次 add a 后，窗口为 a a，关键词 a 的频次为 $2$。第一次 get 1 返回频次最高的唯一关键词 a。

之后每次再执行 add a，都会先淘汰窗口队首的一个旧 a，再把新 a 加入尾部，因此窗口内始终有两个 a，频次保持为 2。

第二次 get 1 时窗口内仍然只有 a，因此再次输出 a。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写