静态区间第 $k$ 小

考虑查询一个集合的第 $k$ 小

在值域 $[l,r]$ 二分答案 $m$，将 $a_i \le m$ 的元素标为 $1$，$a_i > m$ 的元素标为 $0$

记录 $1$ 的个数为 $s$

如果 $s \le k$，说明答案在 $[l,m]$

之后 $a_i > m$ 的元素一直会标成 $0$，故已经没有用了，可以直接删去
如果 $s>k$，说明答案在 $[m+1,r]$

之后 $a_i \le m$ 的元素一直会标成 $1$，故已经没有用了，可以直接删去，并 $k \leftarrow k-s$

也就是说，可以通过二分的答案 $m$，来将原序列拆分成两个新的序列，同时也将所有的询问拆分成两类询问

由于是在二分答案，故每个元素或询问只会下放 $O(\log V)$ 次，故总时间复杂度是 $O(n \log n \cdot T)$

期间可以用排序加二分来代替数状数组的操作

实际上这个划分过程可以做到强制在线

实际上这个过程和划分树有一些异曲同工之处（后者取得不是值域的中位数，而是当前序列的中位数）