今天写 CF 1354D 的时候写 $\mathrm O (n \log^2 n)$ 的树状数组上二分第 k 大的时候写挂了，看了 wiki^[1] 后发现有直接 $\mathrm O (n \log n)$ 求全局第 k 大的科技，遂记之。

主要思想是倍增。

伪代码：

x = 0, sum = 0
for i = log(n) to 1:
	t = range_sum(x + 1...x + 2^i)
	if sum + t < k then
		x = x + 2^i
		sum = sum + t
		
ans = x + 1

容易发现这样得到的 x 是满足 $\sum\limits_{i = 1}^x < k$ 的最大值，所以答案即为 x + 1

int kth(int k) {
    int sum = 0, x = 0;
    for (int i = std::__lg(n); ~i; --i) {
        x += 1 << i;
        if (x >= n || sum + c[x] >= k) {
            x -= 1 << i;
            continue;
        }
        sum += c[x];
    }
    return x + 1;
}