ABC206 C Swappable

まず, 余事象を考える. すると, 条件がない場合のペアの選び方($ \frac{N(N+1)}{2}通り)から$ A_i = A_j(i < j)なる$ (i, j)の個数を引けばよくなる. 後者はmapなどのデータ構造を用いて求めることができる.

よって, この問題を$ O(N \log N)で解くことができた.