对于每一个 $k$，假设能 $\mathcal{O}(1)$ 找出对于一个 $l$，最大的 $r$ 使得 $[l,r]$ 内区间数字的种类数 $\leq k$，就能 $\mathcal{O}(n\log n)$ 解决，因为对于每一个 $k$ 最多会找 $\frac{n}{k}$ 次。

那么现在问题变成快速对于一个 $l$，求一个最大的 $r$ 使得 $[l,r]$ 内区间数字的种类数 $\leq k$，而且要求在线，但对于每个 $k$，$l$ 的询问是递增的。

枚举 $l$，对于 $[l,n]$ 中的每个位置记录它是否是 $[l,n]$ 中第一次出现，区间数字的种类数即为区间和。

现在问题变成了支持单点修改，快速求一个最大的 $r$ 使得 $[1,r]$ 的和 $\leq k$，用树状数组维护前缀和，由于树状数组下标为 $x$ 处存的值为 $(x - lowbit(x),x]$ 区间的和，那么从高到低枚举所求 $r$ 的二进制位 $k$，看是否能够往后跳 $2^k$ ，就能求出这个最大的 $r$ 了。

总的时间复杂度是 $\mathcal{O}(n\log^2n)$。