Particle

競技プログラミングについての雑記

アルゴリズム

選択アルゴリズム

k番目の値を求める。(クエリが複数ある場合は以下の方法では効率が悪い。(e.g. POJ 2104 k-th Number)) アルゴリズム ソート マージソート等の効率のよいソートの計算量はO(nlogn)であるから、O(logn)で求めることができる。 実装略 パーティションベースの…