题解：AT_abc429_c [ABC429C] Odd One Subsequence

题意：

给定长度为 $N$ 的序列 $A$，求有多少三元组 $(i,j,k)$ 满足 $i < j < k$ 且 $A_i,A_j,A_k$ 中恰好有两个数相等（即其余的一个数不相等）。

$1 \leq N \leq 3 \times 10^5, 1 \leq A_i \leq N$。

题解：

实际上我们并不关心数之间的相对顺序，我们记 buc 数组是一个桶，即 buc[i] 表示 $A_j=i$ 的 $j$ 的个数。

统计答案只需要对于每一个 $i$，在 buc[i] 中选择两个数，然后最后一个数不能与 $i$ 相等，即只能有 $n-buc_i$ 个，所以对于每一个 $i$ 的答案就是 $C_{buc_i}^2 \times (n-buc_i)$，然后对于所有的 $i$ 累加就行。