没参加比赛，过来口胡一下。

先假设可以离线。

对右端点 $r$ 进行扫描线，在每个元素最后一次出现处标记上其信息，否则不标记。

然后就是查询从 $l$ 到当前末尾被标记的元素的第 $k$ 小值。

也就是 2-side 矩形查询 $k$ 小值。

我们用权值线段树套位置的线段树，直接在其上二分即可；注意内层树要动态开点。

由于本题强制在线，不能扫描线，我们直接对树套树可持久化一下即可。

时间复杂度 $O((n+q)\log^2n)$，空间复杂度 $O(n\log^2n)$；内层使用可持久化平衡树（应该？）就可以做到 $O(n\log n)$ 空间了。

这题为啥正解是分块啊，怎么回事。

离线可以直接莫队，在线考虑把莫队信息预处理出来不就行了。

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

然后还有另一种做法。

就是二分答案 $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$ 小所在的块然后枚举即可。