k-th number 方法 fractional cascading 実装 プログラムのまとめ まとめ k-th number 数列a_1, a_2, ..., a_nとクエリを表す数の3つ組みがm個与えられる。各クエリ(i, j, k)に対しa_i, ..., a_jを昇順にソートした際のk番目の数を出力せよ。 n ≤ 1000000 m ≤ 5000 |a_i| ≤ 109 2104 -- K-th Number 単純にクエリごとに部分配列の取り出し→ソートを行うと計算量はm * O(n log n) = O(m n log n)です。問題のnの最大値が大きいので計算量をもう少し小さくし…