Count Pairs

組み合わせ$(a_i, a_j)$について、$a_i$を固定して考えます。$\\$ すると、$a_i$に対する相手の種類数は、$i < j \leq N$を満たす$a_j$の種類数だとわかります。 $a_i = X$を満たす複数の$i$がある場合は、最も小さい$i$について考えれば良いです。$\\$ そのため、$a$を右から順に、各$a_i$に対する$a_j$の種類数をunordered_setなどを用いて数えながら更新していけば、全ての$a_i$について相手の種類数がわかります。 $a_i$の相手の種類数をunordered_mapなどで管理すれば、$O(N)$でこの操作を行えます。 最後に、重複を除いた全ての$a_i$について、種類数の和を求めると、これが答えとなります。