K-тартибли статистика

$n$ та сондан иборат массив генератор билан берилади: $a_1 = x$, $i > 1$ учун $a_i = (A \cdot a_{i-1} + B) \bmod M$. Массивни ўсиш тартибида саралаганда $k$-ўринда турадиган сонни топинг (ўринлар $1$ дан бошланади).

Битта қаторда олтита бутун сон: $n$, $k$, $x$, $A$, $B$, $M$ ($$, , ).

Битта сон — $k$-тартибли статистика.

Тўлиқ саралаш $O(n \log n)$, лекин фақат битта ўрин керак бўлса, quickselect (тез танлаш) ўртача $O(n)$ ишлайди: тасодифий таянч атрофида массивни иккига бўлинг ва фақат $k$-ўрин тушган қисмда давом этинг. C++ да бу std::nth_element.

$A \cdot a_{i-1}$ гача етади — кўпайтиришни 64 битли турда бажаринг. Биринчи мисолда массив , сараланган , жавоб .