K-tartibli statistika

$n$ ta sondan iborat massiv generator bilan beriladi: $a_1 = x$, $i > 1$ uchun $a_i = (A \cdot a_{i-1} + B) \bmod M$. Massivni o'sish tartibida saralaganda $k$-o'rinda turadigan sonni toping (o'rinlar $1$ dan boshlanadi).

Bitta qatorda oltita butun son: $n$, $k$, $x$, $A$, $B$, $M$ ($1 \le k \le n \le 3 \cdot 10^6$, $1 \le M \le 10^9$, $0 \le x, A, B < M$).

Bitta son — $k$-tartibli statistika.

To'liq saralash $O(n \log n)$, lekin faqat bitta o'rin kerak bo'lsa, quickselect o'rtacha $O(n)$ ishlaydi: tasodifiy tayanch atrofida massivni ikkiga bo'ling va faqat $k$-o'rin tushgan qismda davom eting. C++ da bu std::nth_element.

$A \cdot a_{i-1}$ $10^{18}$ gacha yetadi — ko'paytirishni 64 bitli turda bajaring. Birinchi misolda massiv $3, 7, 5, 1, 3$, saralangani $1, 3, 3, 5, 7$, javob $3$.