inarizuuuushi https://blog.hatena.ne.jp/inarizuuuushi/ Sabrou-mal サブロウ丸 https://inarizuuuushi.hatenablog.com/ アルゴリズム周辺 python 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の最大値が大きいので計算量をもう少し小さくし… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finarizuuuushi.hatenablog.com%2Fentry%2F2022%2F09%2F05%2F090000" title="フラクショナルカスケーディング応用 - Sabrou-mal サブロウ丸" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/i/inarizuuuushi/20220813/20220813184654.png Hatena Blog https://hatena.blog 2022-09-05 09:00:00 rich https://inarizuuuushi.hatenablog.com/entry/2022/09/05/090000 1.0 100%