Loading problem…
You are given a 0-indexed integer array nums. The distinct count of a subarray of nums is defined as: - Let nums[i..j] be a subarray of nums consisting of all the indices from i to j such that 0 <= i <= j < nums.length. Then the number of distinct values in nums[i..j] is called the distinct count of nums[i..j]. Return the sum of the squares of distinct counts of all subarrays of nums. Since the answer may be very large, return it modulo 10^9 + 7. A subarray is a contiguous non-empty sequence of elements within an array.
Example 1
Input: nums = [1,2,1]
Output: 15
Explanation: The six subarrays have distinct counts 1, 1, 1, 2, 2, 2, so the sum of their squares is 1 + 1 + 1 + 4 + 4 + 4 = 15.
Example 2
Input: nums = [2,2]
Output: 3
Explanation: The three subarrays [2], [2], and [2,2] each have a distinct count of 1, so the sum of their squares is 1 + 1 + 1 = 3.
Example 3
Input: nums = [1,2,3]
Output: 20
Explanation: Single elements give counts 1, 1, 1, the two pairs give 2 and 2, and the whole array gives 3, so the sum of squares is 1 + 1 + 1 + 4 + 4 + 9 = 20.
Grow subarrays by their right end. Each new value bumps the distinct count by one for a contiguous range of start indices, so maintain those counts in a segment tree and track how the running sum of their squares changes.
Run checks all cases above. Submit evaluates all test cases.