JOI2018 予選 F - L番目のK番目の数

• 問題
• AC

0-based($A_0, A_1, ..., A_{N-1}$)で考える。

書き出した数の中に$x$以下の数が$f(x)$個あるとするとき、$f(x) \ge L$となるような最小の$x$を求めればよい。この言い換えを元の数列$(A_i)$の言葉でさらに言い換えると、次のようになる:

$x$以下の数を$K$個以上含むような部分列$A[l, r)$が$L$個以上存在するような$x$の中で最小のものを求めよ。

部分列$A[l, r)$が$x$以下の数を$g(l, r, x)$個含むとする。$x$を固定した時に$、g(l, r, x) \ge K$であるような$l, r \in [0, N]$が何組あるか数えられれば、二分探索で上の$x$も求まりそう。具体的には次のように数える:

$g(0, i, x)$は部分列$A[0, i)$の中の$x$以下の数の総数だから、累積和でテーブルを作っておけば任意の$i$について$O(1)$で求まる。そして、$g(l, r, x) = g(0, r, x) - g(0, l, x) \ge K \Leftrightarrow g(0, r, x) \ge K+g(0, l, x)$であり、$l$を固定した時にこの式を満たすような$r$の数は二分探索で求まる。したがって、すべての$l \in [0, N]$についてこの$r$の数を求めて足し合わせると、それが$f(x)$である。

あとは$f(x)$について二分探索して、$f(x) \ge L$であるような最小の$x$を求めればそれが答えになっている。計算量は${\mathcal O}(N \log^2 N)$。