差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:balancing_binary_search_tree:tree_free [2020/05/26] – [配列・特殊アイデア系①] ikatakos | programming_algorithm:data_structure:balancing_binary_search_tree:tree_free [2020/06/29] – [代替方法一覧] ikatakos | ||
---|---|---|---|
行 27: | 行 27: | ||
* 問題依存の上手い方法 | * 問題依存の上手い方法 | ||
* 列挙していけば何か共通点みたいなのが見つかるかも知れない | * 列挙していけば何か共通点みたいなのが見つかるかも知れない | ||
+ | * %%C++%%コードを埋め込んで外部モジュールとしてコンパイル | ||
+ | * 下記、参考の3つめのリンク参照 | ||
* 参考 | * 参考 | ||
* [[https:// | * [[https:// | ||
* [[https:// | * [[https:// | ||
+ | * [[https:// | ||
行 43: | 行 46: | ||
Binary Indexed Tree で管理できる。ただし、BIT上で累積和の二分探索を実装する必要がある。 | Binary Indexed Tree で管理できる。ただし、BIT上で累積和の二分探索を実装する必要がある。 | ||
- | 詳細は上記サイトまたは[[programming_algorithm: | + | 詳細は[[programming_algorithm: |
* 値 $x$ を追加 → $bit.add(x, 1)$ | * 値 $x$ を追加 → $bit.add(x, 1)$ | ||
行 58: | 行 61: | ||
== 値の範囲がこれを越える場合 === | == 値の範囲がこれを越える場合 === | ||
- | クエリ数が $N=10^6$ | + | 値の取り得る種類数が $N=10^6$ |
== 前後の値を取得 == | == 前後の値を取得 == | ||
行 96: | 行 99: | ||
^機能 | ^機能 | ||
|insert|$O(\log{N})$| | |insert|$O(\log{N})$| | ||
- | |erase |$O(\log{N})$ 下記バリエーション参照| | + | |erase |$O(\log{N})$? 下記バリエーション参照| |
|get_k_th|$O(1)$| | |get_k_th|$O(1)$| | ||
行 111: | 行 114: | ||
== 任意の値を削除せよ == | == 任意の値を削除せよ == | ||
- | 優先度キューとは別に、以下のデータを用意する。 | + | 優先度キューとは別に、「値が生き残っているか」を管理するデータを用意する。 |
* 要素に重複が無い場合 | * 要素に重複が無い場合 | ||
行 137: | 行 140: | ||
Binary Indexed Tree でもいいんだけど、より高速で、なかなかアイデアが綺麗な解法。 | Binary Indexed Tree でもいいんだけど、より高速で、なかなかアイデアが綺麗な解法。 | ||
+ | |||
+ | ++++ これを使って解ける問題(ネタバレ注意) | | ||
+ | |||
+ | * [[https:// | ||
+ | * [[https:// | ||
+ | ++++ | ||
=== std::set解 === | === std::set解 === | ||
行 192: | 行 201: | ||
| | ||
【2番目に大きい要素⑤】 | 【2番目に大きい要素⑤】 | ||
- | 同様に、この時点での⑤の位置における | + | 同様に、この時点での L[i]=3, R[i]=6 が⑤にとっての答え |
i | i | ||
| | ||
行 206: | 行 215: | ||
これを繰り返すと、$O(N)$ で求められる。std:: | これを繰り返すと、$O(N)$ で求められる。std:: | ||
- | ++++ これを使って解ける問題(ネタバレ注意) | | ||
- | * [[https:// | + | === バリエーション === |
- | * [[https:// | + | |
- | ++++ | + | == 順列で無い場合(同じ要素は含まれない) == |
- | 値が順列でなくて飛び飛びなら、(先読みできるなら)圧縮すればよい。 | + | 値が飛び飛びなら、先読みできるなら圧縮すればよい。先読みできない場合は……わからん。 |
- | 注意点として、全ての要素が異なる必要がある点に注意。 | + | == 同じ要素が含まれる場合 == |
同じ値が含まれると、同率の処理が上手くいかない。 | 同じ値が含まれると、同率の処理が上手くいかない。 | ||
- | 一応、自身の値 " | + | 一応、自身の値 " |
+ | |||
+ | * $L[i],R[i]$ の取得を同率の要素ごとにまとめて行い、更新は全ての同率の要素が終わった後で一括に行う | ||
自身の値 " | 自身の値 " |