现在有一个长度为 $5 \times 10^5$ 的数组 $a$（$a$ 中的数 $\le 5 \times 10^5$），有 $5 \times 10^7$ 次操作（假设不考虑输入的时间），每次操作查询一个区间 $[l,r]$ 中数 $x$ 出现了多少次。

这个问题我只会对于每个数记录下标放到 vector 然后二分，但是时间炸了，求复杂度小于 $\mathcal O(m\log n)$（$n=5 \times 10^5, m=5 \times 10^7$）的思路。

另外分块仿佛不行，因为空间限制是 $50\,\text{MB}$。