2916. 子数组不同元素数目的平方和 II
题目描述
给你一个下标从 0 开始的整数数组 nums 。
定义 nums 一个子数组的 不同计数 值如下：
- 令
nums[i..j]表示nums中所有下标在i到j范围内的元素构成的子数组（满足0 <= i <= j < nums.length），那么我们称子数组nums[i..j]中不同值的数目为nums[i..j]的不同计数。
请你返回 nums 中所有子数组的 不同计数 的 平方 和。
由于答案可能会很大，请你将它对 109 + 7 取余 后返回。
子数组指的是一个数组里面一段连续 非空 的元素序列。
示例 1：
输入：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：
输入：nums = [2,2] 输出：3 解释：三个子数组分别为： [2]: 1 个互不相同的元素。 [2]: 1 个互不相同的元素。 [2,2]: 1 个互不相同的元素。 所有不同计数的平方和为 12 + 12 + 12 = 3 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105
解法
方法一
思考
题意与 I 相同，但 \(n \le 10^5\)，枚举子数组并维护集合不可行。将右端点从 \(r-1\) 推到 \(r\) 时，新增的子数组是所有 \([L,r]\)。若 \(x=nums[r]\) 上次出现在 \(p\)，则 \(L \in (p,r]\) 的不同计数加一，从而平方和按 \(2 \cdot \mathrm{cnt}+1\) 增加。
这是对一段下标的区间加，并询问全体平方和，可用懒标记线段树维护「不同计数」与其平方和。按右端扫描，每次在 \((last[x], r]\) 上加一并累加全局平方和。仓库中代码页尚未填入实现，上述结构即该做法的状态与操作顺序。
1 | |
1 | |
1 | |
1 | |