Subarrays distinct element sum of squares ii

Array Dynamic Programming Binary Indexed Tree Segment Tree

22.8% acceptance

Feb 25, 2026

157

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sum_counts(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = nums.len();
    let mut b1 = vec![0i64; n + 2];
    let mut b2 = vec![0i64; n + 2];

    fn badd(b: &mut [i64], mut i: usize, v: i64, sz: usize) {
      i += 1;
      while i <= sz + 1 {
        b[i] = (b[i] + v).rem_euclid(1_000_000_007);
        i += i & i.wrapping_neg();
      }
    }
    fn bsum(b: &[i64], mut i: usize) -> i64 {
      i += 1;
      let mut s = 0i64;
      while i > 0 {
        s += b[i];
        i -= i & i.wrapping_neg();
      }
      s.rem_euclid(1_000_000_007)
    }

    let mut last = std::collections::HashMap::<i32, usize>::new();
    let mut total_f = 0i64;
    let mut total_sq = 0i64;
    let mut ans = 0i64;

    for j in 0..n {
      let prev = last.get(&nums[j]).copied();
      last.insert(nums[j], j);

      let psum = if let Some(p) = prev {
        let s1 = bsum(&b1, p);
        let s2 = bsum(&b2, p);
        ((p as i64 + 1) * s1 - s2).rem_euclid(MOD)
      } else {
        0
      };

      let l = prev.map(|p| p + 1).unwrap_or(0);
      // range_add [l, j] by 1
      badd(&mut b1, l, 1, n);
      if j + 1 <= n { badd(&mut b1, j + 1, -1, n); }
      badd(&mut b2, l, l as i64, n);
      if j + 1 <= n { badd(&mut b2, j + 1, -(j as i64 + 1), n); }

      let prev_idx = prev.map(|p| p as i64).unwrap_or(-1);
      let delta = (j as i64 - prev_idx).rem_euclid(MOD);

      total_sq = (total_sq + 2 * (total_f - psum).rem_euclid(MOD) + delta).rem_euclid(MOD);
      total_f = (total_f + delta).rem_euclid(MOD);
      ans = (ans + total_sq) % MOD;
    }

    ans as i32
  }
}