JOI 18予選 F L番目のK番目の数(難易度8)
$ L
番目に小さい数が
$ X
⇔
$ X
以下の数が
$ L
個以上となるような最小の
$ X
であることを利用して二分探索をしていく.
$ K
番目に小さい数だが, これはさすがに二分探索はできない. 少し考察すると, 尺取り法が適用できる構造になっていることがわかる! よってあとはBITを用いて
$ K
番目に小さい数を高速に求めることで, この問題が解ける.
実装例:
https://atcoder.jp/contests/joi2018yo/submissions/18641468