首先这个题离线直接莫队即可。

然后还有另一种做法。

就是二分答案 $x$，然后数有多少种颜色没有在区间内出现过，即统计 $(i, nxt[i])$ 在 $[1, l - 1][r + 1, n]$ 内的个数，整体二分即可。

在线怎么搞。

莫队寄了。

然后那个二分答案的话要在线三维偏序，空间应该是2log的（如果有1log做法请指正。

出题人写的是值域分块。

记 $s[i][j][k]$ 表示第 $i$ 块到第 $j$ 块内值域第 $k$ 块出现的颜色数，记 $app[i][j]$ 表示前 $i$ 块内 $j$ 出现的次数。

我们要知道什么？我们要知道值域第 $k$ 块在 $[l, r]$ 区间内出现了几个，以及 $x$ 这个颜色有没有在 $[l, r]$ 内出现。

后者是容易的，而前者呢。

我们用零散块内的元素去更新整块区间的 $s$。

具体地，设整块区间为第 $l$ 块到第 $r$ 块，开一个 $cnt$ 数组，若当前元素 $x$ 的 $cnt[x] = 0$ 且在 $[l, r]$ 这几个整块内没有出现过，那就更新 $s[l][r][belong[x]]$，然后给 $cnt[x]$ 加一。

查询时找到第 $k$ 小所在的块然后枚举即可。