Equalizing by Division (hard version)
题意翻译
## 题目描述
简单版和困难版之间的唯一区别在于数组元素的数量。
给定一个数组$a$,包含$n$个整数。每次操作你可以选择任一$a_i$并且将其除$2$向下取整(也就是说,每次操作中你可以使$a_i:=\lfloor \frac{a_i}{2} \rfloor$)。
你可以对任何$a_i$进行任意次(可以是零次)操作。
你的任务是计算最小的操作次数使得至少$k$个数组中的数字相等。
别忘了在几次操作后可能会有$a_i=0$的情况出现,因此答案始终存在。
## 输入格式
输入的第一行包含两个整数$n$和$k$($1\le k\le n\le 2 \cdot 10^5$)——数组中的元素个数和需要相等的数字个数。
输入的第二行包含$n$个整数$a_i,a_2,\cdots , a_n$($1\le a_i\le 2 \cdot 10^5$),其中$a_i$为$a$中的第$i$个元素。
## 输出格式
输出一个整数——使得数组中有$k$个相等的数的最小操作次数。
题目描述
The only difference between easy and hard versions is the number of elements in the array.
You are given an array $ a $ consisting of $ n $ integers. In one move you can choose any $ a_i $ and divide it by $ 2 $ rounding down (in other words, in one move you can set $ a_i := \lfloor\frac{a_i}{2}\rfloor $ ).
You can perform such an operation any (possibly, zero) number of times with any $ a_i $ .
Your task is to calculate the minimum possible number of operations required to obtain at least $ k $ equal numbers in the array.
Don't forget that it is possible to have $ a_i = 0 $ after some operations, thus the answer always exists.
输入输出格式
输入格式
The first line of the input contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 2 \cdot 10^5 $ ) — the number of elements in the array and the number of equal numbers required.
The second line of the input contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 2 \cdot 10^5 $ ), where $ a_i $ is the $ i $ -th element of $ a $ .
输出格式
Print one integer — the minimum possible number of operations required to obtain at least $ k $ equal numbers in the array.
输入输出样例
输入样例 #1
5 3
1 2 2 4 5
输出样例 #1
1
输入样例 #2
5 3
1 2 3 4 5
输出样例 #2
2
输入样例 #3
5 3
1 2 3 3 3
输出样例 #3
0