多重集合の実装方法とそれぞれのユースケース

• ソートされた Vec
  • 区間最小値や区間要素数などは Vec でもできる
  • k 番目取得もできる
  • BTreeMapと違って、変更に弱い
• PriorityQueue (BinaryHeap)
  • 最大値の取得・削除と挿入だけできれば良い場合は BTreeMap より高速
• HashMap
  • 基本は HashMap でよい。
• BTreeMap
  • どれか1つの値を取得したい場合（HashMap だと遅い可能性がある）
  • 全体やある範囲での max/min を取得
  • ある範囲に値があるかを判定
• FenwickTree
  • ある区間に含まれている個数の取得
  • 全体やある範囲での k 番目の値の取得
  • エントリーされる値はあらかじめわかる（エントリー可能な値は初期化の段階で決める必要がある）

多重集合の数え上げ

重複組合せ

メモ

• 多重集合は自由可換モノイドの元
• 可換モノイドの集約値を差分計算で場合は多重集合を持たせておくといいがち。
  • モノイドに逆元がなくてもうまくいく。
  • 例
    • ABC445 E - Many LCMs
• しゃくとり法 は多重集合と親和性がいいがち
• 多重集合は頻度で表すのとソートされた列で表すのの2パターンがある
• 多重集合の一致判定は Zobrist Hash でできる: ハッシュ
• ABC381 E - 11/22 Subsequence

https://atcoder.jp/contests/abc367/tasks/abc367_f ソートして一致:多重集合として一致