题解

思路

题目的核心是动态维护当前区间中“每种股票的出现次数”这一多重集合。小规模可直接重算，整段支线可只算一次；满分做法使用莫队移动区间，再在频率轴上分块选择第 $k$ 小值。

做法

1. 小规模直接统计

对每个询问扫描区间，用映射统计每个股票编号的出现次数，将所有正频率排序后取第 $k$ 个。复杂度为 $O(MN\log N)$，适用于 $N,M\le1000$。

2. 全区间支线

若所有询问均为 $[1,N]$，只需统计一次整段序列的频率并排序。每个询问直接访问排序后的数组，复杂度为 $O(N\log N+M)$。

3. 莫队维护区间

先离散化股票编号，并离线按莫队顺序排列询问。移动左右端点时维护：

• cnt[x]：股票 $x$ 在当前区间内的出现次数；
• number[f]：恰好出现 $f$ 次的股票种类数。

加入一个股票时，若其旧频率为 $f>0$，先令 number[f] 减一；随后频率变为 $f+1$，令 number[f+1] 加一。删除操作完全对称。因此，任意时刻所有正频率的多重集合都由 number 精确表示。

将频率轴再按平方根分块，维护每个频率块中的股票种类总数。回答第 $k$ 小频率时先跳过整块，再在目标块内逐个频率查找。若当前不同股票数少于 $k$，答案为 $-1$。

正确性证明

端点每移动一步，上述加入或删除操作恰好删除旧频率的一份贡献，并加入新频率的一份贡献，所以 number[f] 始终等于当前区间内热度为 $f$ 的股票种类数。按频率从小到大累加这些种类数，首次使前缀和达到 $k$ 的频率，正是所有股票热度排序后的第 $k$ 个值。莫队仅改变处理询问的顺序，不改变每个询问对应的区间，故所有答案正确。

复杂度

设块长为 $B=\Theta(\sqrt N)$。莫队端点移动总量为 $O((N+M)\sqrt N)$，每次移动为 $O(1)$；每次第 $k$ 小查询为 $O(\sqrt N)$。总复杂度为 $O((N+M)\sqrt N)$，空间复杂度为 $O(N+M)$。