在许多信息学竞赛问题中，往往复杂度瓶颈在于排序（例如虚树按照 $\mathtt{\text{dfn}}$ 排序时），能否优化至线性呢？

可以类似桶排序的思路做到单组 $\mathcal{O}(n+V)$，但是这显然太耗时间了，发现桶排序扫描的过程需要执行 $T$ 次，而 $\mathcal{O}(n)$ 却是不可避免的，所以考虑优化扫描桶的过程。

所以可以在每个桶上开一个 $\mathtt{\text{vector}}$，表示包含这个数的询问编号，最终只需离线下来扫描一次。

由于放入桶中的数有 $\sum n$ 个，所以扫描桶的复杂度是 $\mathcal{O}(\sum n+V)$ 的，总时间复杂度是 $\mathcal{O}(\sum n+V)$ 的。

这个算法可能没有太大的应用，以后可以考虑在这上面出 (ka) 出 (ka) 题 (chang) 卡掉一个 $\mathcal{O}(\log n)$（虽然这常常不是瓶颈）。

upd：应讨论区 @Linshey 提醒，在桶上不一定要用 $\mathtt{\text{vector}}$ 维护，可以用类似链表等数据结构维护，常数是没有问题的。