P3730 题解 最后更新于 2025-05-02 00:00:18

## 题意 离线询问区间出现次数第 $k$ 少的颜色的出现次数。 ## 思路 先离散化，然后分成两步做。 1. 莫队 做莫队的时候修改记录三个东西：第 $i$ 种颜色出现次数；出现 $i$ 次的颜色种数；颜色种数分块结果。这个东西应该很好搞。 2. 值域分块 前面记录的分块结果拿来用。每次询问中，先扫描 $\sqrt{n}$ 段，找到在第几段时答案超过了本次询问的 $k$ ，时间 $\sqrt{n}$ ; 然后在这一段中暴力找第 $k$ 个，这段也是 $\sqrt{n}$ 的。 然后做完了，时间复杂度 $O(n\sqrt{n})$ 。常数可能有点大，但luogu神机最大点只跑了400多ms。