给你一个下标从 0 开始的整数数组 nums 。
定义 nums 一个子数组的 不同计数 值如下：
- 令
nums[i..j]表示nums中所有下标在i到j范围内的元素构成的子数组（满足0 <= i <= j < nums.length），那么我们称子数组nums[i..j]中不同值的数目为nums[i..j]的不同计数。
请你返回 nums 中所有子数组的 不同计数 的 平方 和。
由于答案可能会很大，请你将它对 10^9 + 7 取余 后返回。
子数组指的是一个数组里面一段连续 非空 的元素序列。
示例 1：
```txt
输入：nums = [1,2,1]
输出：15
解释：六个子数组分别为：
[1]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[1]: 1 个互不相同的元素。
[1,2]: 2 个互不相同的元素。
[2,1]: 2 个互不相同的元素。
[1,2,1]: 2 个互不相同的元素。
所有不同计数的平方和为 12 + 12 + 12 + 22 + 22 + 22 = 15 。
```
示例 2：
```txt
输入：nums = [2,2]
输出：3
解释：三个子数组分别为：
[2]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[2,2]: 1 个互不相同的元素。
所有不同计数的平方和为 12 + 12 + 12 = 3 。
```
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^5
子数组不同元素数目的平方和 II
题目
给你一个下标从 0 开始的整数数组 nums 。
定义 nums 一个子数组的 不同计数 值如下：
- 令
nums[i..j]表示nums中所有下标在i到j范围内的元素构成的子数组（满足0 <= i <= j < nums.length），那么我们称子数组nums[i..j]中不同值的数目为nums[i..j]的不同计数。
请你返回 nums 中所有子数组的 不同计数 的 平方 和。
由于答案可能会很大，请你将它对 10^9 + 7 取余 后返回。
子数组指的是一个数组里面一段连续 非空 的元素序列。
示例 1：
1 | 输入：nums = [1,2,1] |
示例 2：
1 | 输入：nums = [2,2] |
提示：
-
1 <= nums.length <= 10^5 1 <= nums[i] <= 10^5
题解
方法一：
思路
对于子数组中值不同的个数为x，求所有子数组的x的平方和。
设$f_{l,r}$为区间[l,r]中不同值的个数。答案是$\sum \limits_{r=0}^{n-1}\sum \limits_{l=0}^{r} f_{l,r}^2$。
我们先考虑简单的版本$\sum \limits_{r=0}^{n-1}\sum \limits_{l=0}^{r} f_{l,r}$
我们考虑固定右端点的所有子数组不同值的个数。看右端点增大时有什么规律。
已知$\sum \limits_{i=0}^{r} f_{i,r}$，求$\sum \limits_{i=0}^{r+1} f_{i,r+1}$
假设nums[r+1]最近出现的下标是t，我们发现从下标t+1到r+1作为子数组的左端点，r+1作为右端点。相对于r作为右端点，都新增了一个从未出现的数。
对于下标r+1只需要用线段树让区间[t+1, r+1]的增长1，然后求区间[0,r+1]的总和。这就是以r+1作为右端点的贡献。所有下标作为右端点的贡献累加起来就得到了$\sum \limits_{r=0}^{n-1}\sum \limits_{l=0}^{r} f_{l,r}$。
我们要求$\sum \limits_{r=0}^{n-1}\sum \limits_{l=0}^{r} f_{l,r}^2$。
对于一个区间内的数都增长k，其平方和如何计算呢？
$\sum \limits_{i=l}^{r} (a_i+k)^2 = \sum \limits_{i=l}^{r} a_i^2 + 2k\sum \limits_{i=l}^{r} a_i + (r-l+1) k^2$
我们只需用线段树维护区间和以及区间平方和，利用以上公式进行更新即可。
代码
1 |
|