Hey guys!
Today I want to ask about this problem.
Given an array A size N and q queries. (|A[i]| <= 1e5, N <= 1e5, q <= 1e5)
Define F(B), B is a subarray (consecutive) of array A, is the number of distinct values of B. For example: F({1, 2, 3, 4}) = 4
For every query i x, change value A[i] to x, and calculate the sum of all F(B) in the new array A. For a query when A = {1, 1, 2}
- F({1}) = F({1}) = F({2}) = F({1, 1}) = 1;
- F({1, 2}) = F({1, 1, 2}) = 2;
The sum result is 1 * 4 + 2 * 2 = 8;
Test: Input
4
1 2 3 4
3
1 1
2 1
3 1
Output
20
17
13
For the first part of this problem, you can probably make a segment tree which contains a set at each of its nodes.
I'm not entirely sure about the second part (sum of all subarrays), but I might have seen a similar problem in the segment tree EDU section before.
I don't see how your idea would work without spending a lot of time merging sets for each query.
Make an array $$$B$$$ such that $$$B[i]$$$ is the least $$$j > i$$$ with $$$A[i] = A[j]$$$ or $$$\infty$$$ if such $$$j$$$ doesn't exist. It is easy to see that an update to $$$A$$$ triggers $$$O(1)$$$ updates to $$$B$$$.
Now the queries become "count elements in range $$$l \ldots r$$$ with $$$B[i] > r$$$" which you can solve with sone 2D stuff.
What is $$$l$$$ and $$$r$$$?
The number of distinct elements in the subarrayis the same asthe number of elements in the subarray that are the first with their value.So we can reverse the order of counting and for each element $$$i$$$ calculate the number of subarrays where there is no same element to the left. If we know $$$left(i)$$$ which is the largest $$$j<i$$$ with $$$A[j]=A[i]$$$ (or $$$0$$$ if there is no such $$$j$$$) then the number of such subarrays is $$$(i-left(i)) \times (n-i+1)$$$.
As -is-this-fft- stated, an update will change at most three $$$f(i)$$$, so you can maintain them in set and simply recalculate the contribution of changed values.