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

题意

对于任意数组，其分数为其中值相等的对数。问他的所有子数组的以及其自身的分数总和。

题解

显然，我们把相同的数放在一起。于是我们得到一个值相同的下标的数组。以样例为例，我们会得到两个下标数组：[0,2,3]和[1]。

于是我们考虑处于某一个位置的某个数作为配对中的后一位的所有可能数。以第3个1为例。对于字串的区间[l,r]，对于(2,3)这种配对，只要有$l\leq 2$，$r \geq 3$，这个配对就能成立。于是共有$3\cdot 1 = 3$种可能。
于是对于某个下标数组$a$，其分数为$\sum_{i}\sum_{j=0}^{(i-1)}{(n-a[i])\cdot (a[j]+1)}$。其中$(n-a[i])$是固定值，于是化简一下得到$\sum_{i}[(n-a[i])\cdot\sum_{j=0}^{(i-1)}{(a[j]+1)}]$。于是可以用前缀和提前求出$\sum_{j=0}^{(i-1)}{(a[j]+1)}$的值。

代码

Java

C++