Codeforces Round #721 Sequence Pair Weight Solution (Java/C++)

Solution:

We put the same numbers together. Then we get the index array of same numbers. For example, for [1,2,1,1], we put same number together, so, we get: [0,2,3] and [1].

Then, let us consider the number of pairs that the second one of the pair is the index i. (For example, for the 3rd 1, about the range of subarray [l, r], and for the pair (2,3), if and only if $l\leq 2$ and $r \geq 3$, this pair is valid.)
So, for the index array $a$, the weight is $\sum_{i}\sum_{j=0}^{(i-1)}{(n-a[i])\cdot (a[j]+1)}$. And for fixed i, the $(n-a[i])$ is fixed. So, the weight is $\sum_{i}[(n-a[i])\cdot\sum_{j=0}^{(i-1)}{(a[j]+1)}]$. And we can get the $\sum_{j=0}^{(i-1)}{(a[j]+1)}$ by pre-process.

Code:

Java

C++