Leetcode Problem 2916. Subarrays Distinct Element Sum of Squares II

2916. Subarrays Distinct Element Sum of Squares II

Leetcode Solutions

Segment Tree with Range Update

  1. Initialize a segment tree that can handle range updates and queries.
  2. Initialize a dictionary to keep track of the last occurrence of each element in the array.
  3. Initialize a variable to keep the running sum of the squares of the distinct counts.
  4. Iterate through the array from left to right.
  5. For each element, find the last occurrence index from the dictionary.
  6. Update the segment tree for the range from the last occurrence index + 1 to the current index.
  7. Query the segment tree to get the sum of the distinct counts for the range from the last occurrence index + 1 to the current index.
  8. Update the running sum with the square of the new distinct count.
  9. Update the last occurrence of the current element in the dictionary.
  10. Return the running sum modulo 10^9 + 7.
UML Thumbnail

Maintain Sorted List of Next Occurrence and Keep Track of Sum of Squares

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...