ABC206 C Swappable
まず,
余事象を考える
. すると, 条件がない場合のペアの選び方(
$ \frac{N(N+1)}{2}
通り)から
$ A_i = A_j(i < j)
なる
$ (i, j)
の個数を引けばよくなる. 後者はmapなどのデータ構造を用いて求めることができる.
よって, この問題を
$ O(N \log N)
で解くことができた.
実装例:
https://atcoder.jp/contests/abc206/submissions/23574020