頻度表

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

頻度→三角数

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

多重集合、multiset