静态区间第 \(k\) 小，强制在线。
设原数组长度为 \(n\) ，值域为 \(V\) 。
首先我们 \(kth\) 转 \(rnk\) ，给定 \((l, r, x)\) ，查询数组 \(a[l \ldots r]\) 中 \(<x\) 的数量，强制在线。
\(rnk\) 做法一
再差分简化一下问题。给定 \((r, x)\) ，查询 \(a[1 \ldots r]\) 中 \(< x\) 的数量，强制在线。
设 \(n\) 棵线段树，第 \(i\) 棵线段树 \(T_i\) ，每一棵线段树大小为 \(V\) （动态开点优化）。
其中， \(T_i\) 维护原数组 \(a[1 \ldots i]\) 这个前缀上的权值数组信息。
不难发现，\(T_{i + 1}\) 可以由 \(T_i\) 单点修改一次得到，所以用可持久化线段树维护所有 \(T\) 。
对于查询 \((r, x)\) ，查询 \(T_r\) 上 \([1 \ldots x - 1]\) 的区间和即可。
\(rnk\) 做法二
设 \(V\) 棵线段树，第 \(i\) 棵线段树 \(T_i\) ，每一棵线段树大小为 \(n\) 。
其中， \(T_i\) 所维护的数组 \(b\) 满足 \(b_i = [a_i < x]\)
\(T_{i+1}\) 也可以由 \(T_i\) 单点修改若干次得到，整个单点修改过程不超过 \(n\) 次，所以也可以用可持久化线段树维护。
对于查询 \((l, r, x)\) ，查询 \(T_{x}\) 上 \([l \dots r]\) 的区间和即可。
显然实际我们不可能用 \(V\) 棵线段树……离散化一下就能做到 \(n\) 棵了。 注意查询的 \(x\) 也要离散化。
\(kth\)
正常来讲，解决 \(rnk\) 问题之后，直接来解决 \(kth\) 会多个 \(log\) 。也即，我们二分 \(x\) ，对 \(x\) 求 \(rnk\) ，从而找到 \(rnk = k\) 的那个 \(x\) 。
但是线段树和树状数组可以把这个 \(log\) 整掉。一个例子是 \(SHOI2015\) 脑洞治疗仪。
为此，我们直接在线段树上跑二分，而不是先二分再查询。
我们选择 \(rnk\) 做法一的做法来建立线段树。那么对于一次 \((l, r, k)\) 的查询，我们应该同时在 \(T_{l-1}\) 和 \(T_r\) 两个线段树跑。
假设我们遍历到 \(T_{l - 1}\) 和 \(T_r\) 上位置相同的节点，对应的相同的 \(a\) 下标区间 \([L, R]\) 。
那么 \(T_r\) 在这个节点上的信息（\([L, R]\) 区间和）减去 \(T_{l - 1}\) 在这个节点上的信息，就可以得到 \(a[l \ldots r]\) 中大小在 \([L, R]\) 内的数量。
试想，我们想知道 \(a[l \ldots r]\) 的第 \(3\) 小，且 \(V = 5\)（即值域 == 线段树大小为 \(5\) ）。
我们首先查询，比如，得知 \(a[l \ldots r]\) 中大小在 \([1, 3]\) 内的数量为 \(2\) 。
那就相当于我们要查询 \(a[l \ldots r]\) 中大小在 \([4, 5]\) 内的第 \(3 - 2 = 1\) 小。
而如果，我们得知 \(a[l \ldots r]\) 中大小在 \([1, 3]\) 内的数量为 \(4\) 。
那就相当于我们要查询 \(a[l \ldots r]\) 中大小在 \([1, 3]\) 内的第 \(3\) 小。
形式化：我们想知道 \(a[l \ldots r]\) 中大小在 \([L, R]\) 内的第 \(k\) 小，那就先查询 \(a[l \ldots r]\) 中大小在 \([L, \mathrm{mid}]\) 内的数量 \(s\) 。
如果 \(k \le s\)，那么就递归查询 \(a[l \ldots r]\) 中大小在 \([L, \mathrm{mid}]\) 内的第 \(k\) 小；
如果 \(k > s\) ，那么就递归查询 \(a[l\ldots r]\) 中大小在 \([\mathrm{mid} + 1, R]\) 内的第 \(k - s\) 小。
一直到递归叶子 \(L = R\) 的时候，一定正好是查询这个叶子的第 \(1\) 小，直接返回这个叶子的下标 \(L\) ，代表答案就是 \(L\) 。