Official
D - Distinct Trio Editorial by en_translator
The condition can be rephrased as follows: “find the number of triplets \((i,j,k)\) such that \(A_i < A_j < A_k\).”
details
For a triplet $(i,j,k)$ satisfying the original condition, there exists a unique permutation of $i,j,k$ such that $A_i \lt A_j \lt A_k$. Conversely, for a triplet $(i,j,k)$ such that $A_i\lt A_j\lt A_k$, there exists a unique permutation of $i,j,k$ such that $i\lt j\lt k$.Consider exhaustively enumerating \(j\). Then, \(i\) and \(k\) can be chosen independently. The number of choices for \(i\) is the number of elements of \(A\) with values smaller than \(A_j\), and the number of choices for \(k\) is the number of elements of \(A\) with values larger than \(A\). Therefore, this problem can be solved in a total of \(O(N+\max A)\) time by preparing an array of “how many elements of \(A\) is less than \(x\)?”.
posted:
last update: