The square is the whole difficulty. Drop it and you get Total Appeal of A String (2262), where every value is charged separately: each index pays for the windows in which it is the first of its kind, and the answers add up. Squaring kills that. The square of a sum keeps the cross terms between two different values, and there is no honest way to bill those to one index. So I stopped decomposing by value and started sweeping the right endpoint. Fix `j` and let `d[i]` be the distinct count of `nums[i..j]` for every `i <= j`. The answer is the running total of `sum(d[i]^2)` read once per `j`. Pushing the endpoint from `j-1` to `j` raises `d[i]` by exactly one for `i` in `(prev[nums[j]], j]`, where `prev` is the last earlier index holding the same value — one contiguous range, and nothing outside it moves. That is what makes the sweep affordable, because `(d+1)^2 = d^2 + 2d + 1`. A segment tree node that stores both `sum(d)` and `sum(d^2)` over its segment can absorb a uniform range add in constant work, so each endpoint costs O(log n). The naive instinct — rebuild `d` from scratch for every `j`, or just enumerate subarrays, which is what the Easy twin 2913 lets you get away with — is quadratic, and `n` up to `10^5` means roughly `5 * 10^9` subarrays. ### Worked example `nums = [1,2,1]`, with `d` shown after each endpoint: - `j = 0`: `prev[1] = -1`, add 1 over `[0,0]` → `d = [1]`, squares `1`, total `1`. - `j = 1`: `prev[2] = -1`, add 1 over `[0,1]` → `d = [2,1]`, squares `4 + 1 = 5`, total `6`. - `j = 2`: `prev[1] = 0`, add 1 over `[1,2]` → `d = [2,2,1]`, squares `4 + 4 + 1 = 9`, total `15`. The third step is the one worth watching: `d[0]` stays at 2 because the subarray `nums[0..2]` already contained a 1, and the range add starts past that occurrence. ### Complexity - Time O(n log n) — one range add and one root read per endpoint. - Space O(n) — four flat arrays of `4n` for the tree, plus a `10^5` last-seen table instead of a hash map, since `1 <= nums[i] <= 10^5` makes direct indexing legal. ### Code (C++) ```cpp class Solution { static const long long MOD = 1000000007LL; int n; vector s1, s2, lz, len; void build(int node, int l, int r) { len[node] = r - l + 1; if (l == r) return; int m = (l + r) >> 1; build(node << 1, l, m); build(node << 1 | 1, m + 1, r); } // every d[i] in this node grows by v: (d+v)^2 = d^2 + 2vd + v^2 void addAll(int node, long long v) { s2[node] = (s2[node] + 2 * v % MOD * s1[node] + v * v % MOD * len[node]) % MOD; s1[node] = (s1[node] + v % MOD * len[node]) % MOD; lz[node] = (lz[node] + v) % MOD; } void push(int node) { if (lz[node]) { addAll(node << 1, lz[node]); addAll(node << 1 | 1, lz[node]); lz[node] = 0; } } void update(int node, int l, int r, int ql, int qr) { if (qr < l || r < ql) return; if (ql <= l && r <= qr) { addAll(node, 1); return; } push(node); int m = (l + r) >> 1; update(node << 1, l, m, ql, qr); update(node << 1 | 1, m + 1, r, ql, qr); s1[node] = (s1[node << 1] + s1[node << 1 | 1]) % MOD; s2[node] = (s2[node << 1] + s2[node << 1 | 1]) % MOD; } public: int sumCounts(vector& nums) { n = nums.size(); s1.assign(4 * n, 0); s2.assign(4 * n, 0); lz.assign(4 * n, 0); len.assign(4 * n, 0); build(1, 0, n - 1); vector last(100001, -1); long long ans = 0; for (int j = 0; j < n; ++j) { update(1, 0, n - 1, last[nums[j]] + 1, j); last[nums[j]] = j; ans = (ans + s2[1]) % MOD; } return (int)ans; } }; ``` ### One note Both traps live in the three lines of `addAll`. The first is order: `s2` has to be rewritten before `s1`, because `s2 + 2*v*s1 + v*v*len` needs the pre-update `sum(d)`. Swap the two assignments and the tree inflates on the very first add — a fresh leaf with `v = 1` reports `3` instead of `1`, so even Example 1 breaks. The second is where `% MOD` sits in `v * v % MOD * len[node]`. The lazy tag accumulates mod `10^9+7`, so `v` can sit near `10^9` by itself; `v * v` is then around `10^18`, and multiplying that by a segment length of `10^5` before reducing overflows `long long` in silence. Reducing first keeps the product near `10^14`. For comparison, the neighbouring `2 * v % MOD * s1[node]` is safe either way, which is exactly why the asymmetry is easy to miss. Carry-away: when a problem squares an aggregate, look for a sweep where the aggregate changes uniformly over a contiguous range, then store one extra moment (`sum(d)` next to `sum(d^2)`) so the square can be updated in closed form. The same pair of aggregates handles range-add plus query-variance, and it is a cheaper reflex than reaching for a heavier structure. 413 ms and 296.8 MB here — the memory sits in the bottom decile, and keeping the tree in 32-bit values while widening only inside the arithmetic would be the obvious trim.