NISHIO Hirokazu[Translate]
頻度表
N個の数があって、Nが大きすぎてO(N^2)ができない時
数の順序に意味がなく、数の種類がNよりだいぶ少ないMなら
種類別の頻度表を作ることで計算量を減らせる

頻度→三角数
N個の数から2つ選ぶペアについて、二つが同じ値であるものをカウントするケース
素朴にループするとO(N^2)
頻度を数えて、各値の頻度nごとに三角数T_{n-1} = n(n-1)/2
これならO(N)

多重集合、multiset

Related Pages

  • →操作の結果が同一になる条件×xであるものの数え上げ→xならば？×余事象を引く×頻度→三角数×列の範囲更新×操作の結果の数え上げ→
  • AGC019B
  • →操作の順番によらない×三角数×値域と定義域の交換→
  • ARC109
  • →蟻本×binary_lndexed_tree×bit×fenwick_tree×値域と定義域の交換×multiset×座標圧縮×データ構造→
  • フェニック木
  • →動的計画法×期待値dp×DP J×順序のない列は多重集合×多重集合×所要時間期待値dp→
  • DP J
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]