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

先假设可以离线。

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

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

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

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

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

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

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