考え方だけメモ． 考え方 回答例 考え方色の区別がない場合に必要な入れ替え操作の回数は，「自分より小さいのに自分よりあとに現れる数」の（すべての「自分」に関する）総和となる（AtCoder Beginner Contest 261 - YouTube）．後ろから見ていけばBITで反…

優先度付きキュー 考え方 回答例 参考 BIT 考え方 回答例 優先度付きキュー考え方$K$要素のリストを管理し， 「(リストの中で一番小さい値) そうでないなら，リストを変更しない とすれば，このリストの最小値が各ステップで求めたい値となる．これは，最初…

【関連】 ABC231F - Jealous Two - 競プロはじめました 考え方 回答例 考え方ABC231Fと類似の考え方．ただし，BITで区間和を取るのではなく，区間の最大値を求める．最大値を求めるように，BIT (Binary Indexed Tree (BIT) / Fenwick Tree - 競プロはじめま…

【関連】 D - プレゼント (ABC038D - プレゼント - 競プロはじめました) 考え方 回答例 参考 考え方$A$の昇順・$B$の降順で見ていく．絵を書くとわかりやすい．各$B_{i}$に対し， bit[i] += 1とし， ans +=$\sum_{j (\geq i)} \mathrm{bit\,} [j]$としていく…

フェニック木 (Fenwick tree) とも呼ばれます． 基本形（区間和） 機能 実装例 例題 応用（最大・最小・XORなど） 機能 実装例 例題 応用（二分探索→ある要素が何番目に大きいかがわかる） 参考 基本形（区間和）機能数列$a_{1},a_{2},...,a_{N}$があったと…