树状数组倍增
所需变量
a i a_i ai 离散化后，第 i i i 个数出现过的次数。
t r e e i tree_i treei 树状数组。
思路
一个简单的常识，每个数的排名，等于小于它的数的数量，也就是 ( ∑ k = 1 n a i ) + 1 (\sum_{k = 1}^{n} a_i)+1 (∑k=1nai)+1。
要求排名第 k k k 的数，其实就是 k k k 的最大值。
也就是 ( ∑ k = 1 n a i ) + 1 ≤ k − 1 (\sum_{k = 1}^{n} a_i)+1 \leq k-1 (∑k=1nai)+1≤k−1。
左边边可以用树状数组来求，枚举一个 r r r，最大的就是 k − 1 k-1 k−1 了。这个地方就要用到倍增了。
树状数组第 i i i 位 ∑ j = i − l o w b i t ( i ) + 1 i a i \sum_{j=i-lowbit(i)+1}^{i} a_i ∑j=i−lowbit(i)+1iai。
我们可以倍增枚举 2 l o g n , 2 l o g n − 1 , . . . , 1 2^{log_n},2^{log_{n-1}},...,1 2logn,2