题解

思路

按右端点从左到右统计。固定右端点 $r$，记所有以 $r$ 结尾的子数组的不同元素个数为 $D_l=f(l,r)$，需要维护 $S_r=\sum_{l=1}^{r}D_l^2$。

设 $p$ 是 $A_r$ 上一次出现的位置；若此前没有出现，则 $p=0$。加入 $A_r$ 后，左端点在 $[p+1,r]$ 内的子数组恰好新增一种不同元素，其余子数组不变。因此

$$S_r=S_{r-1}+2\sum_{l=p+1}^{r}D_l^{\mathrm{old}}+(r-p).$$

这里令加入新位置前的空子数组对应值为零。

考虑某个此前出现过的值，设它最后出现于位置 $t$。它会对 $D_l^{\mathrm{old}}$ 贡献一，当且仅当 $l\le t$。所以它对区间 $l\in[p+1,r]$ 的总贡献是 $\max(0,t-p)$。于是所需的旧值之和为

$$\sum_{t>p}(t-p)=\sum_{t>p}t-p\cdot\#\{t>p\},$$

其中每种不同的值只保留其最后出现位置。

做法

分别用两棵树状数组维护所有当前最后出现位置的数量和位置之和。处理 $A_r$ 时，在后缀 $(p,n]$ 上查询数量与位置和，代入上式更新 $S_r$，再将 $S_r$ 加入总答案。随后删除旧位置 $p$，插入新位置 $r$。

当 $n\le100$ 时，可以枚举左端点并逐步扩展右端点，用集合维护不同值数量。

若所有元素相等，每个子数组的 $f$ 都是一，答案为子数组总数 $n(n+1)/2$。

若所有元素互不相同，长度为 $L$ 的子数组有 $n-L+1$ 个且 $f=L$，求和可化为

$$\sum_{L=1}^{n}(n-L+1)L^2=\frac{n(n+1)^2(n+2)}{12}.$$

正确性说明

加入 $A_r$ 时，只有不包含其上一次出现位置的子数组会增加一种不同元素，因此受影响左端点恰为 $[p+1,r]$。平方差恒为 $(D+1)^2-D^2=2D+1$，故转移式正确。

对任意旧值，只保留最后出现位置 $t$ 即可判断它是否出现在子数组 $[l,r-1]$ 中；它在所有受影响左端点中的贡献次数正是 $\max(0,t-p)$。两棵树状数组精确维护这些最后位置的数量与和，所以每次得到的旧值之和正确。逐个累加所有 $S_r$ 即覆盖且只覆盖全部子数组。

复杂度

离散化需要排序。每个位置执行常数次树状数组操作，总时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。