[問題案] Kth Smallest

[SSRS-cp]

問題名: Kth Smallest 問題 ID: kth_smallest 想定アルゴリズム: median of medians

問題文

長さ N の数列 a_0, a_1, ..., a_{N-1} と整数 k が与えられる。(a_0, a_1, ..., a_{N-1}) のうち k+1 番目に小さい値を求める。

制約

1<=N<=5*10^5 0<=a_i<=10^9 0<=k<N

[tko919]

Range Kth SmallestにQ=1,L=0,R=Nのケースを追加すれば兼用できそうです

[yosupo06]

↑のtkoさんのやつか、もしくはk番目取得よりは1-k番目取得の方がよく見るトピックな気がします

[yosupo06]

結果ははsortされてなくてもいいというやつです(O(N)でできるという話

[maspypy]

特にこれを verify したいという話を（問題提案者を含めて）見かけていないため、優先度は低そうですが、準備に興味がある型が居ればお願いします。